# Undirected, connected and weighted graph implementation

I was thinking in a way of implementing a graph in such that would let find a minimum spanning tree.

I have this:

Graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include <list>
#include <vector>
#include <utility>
#include <iostream>
#include <map>
#include <queue>

using namespace std;

template <class KeyType, class WeightType>
class Graph
{
public:
class Edge;
class Vertex;
typedef typename list<Vertex>::iterator VertexIt;
typedef typename list<Edge>::iterator EdgeIt;

class Vertex
{
friend class Graph;

Vertex(const KeyType& k);

list<EdgeIt> incEdges;
KeyType key;
};

class Edge
{
friend class Graph;

Edge(const pair<VertexIt, VertexIt>& vp, const WeightType& w);

pair<VertexIt, VertexIt> incVertices;
WeightType weight;
};

{
Link(const pair<KeyType, KeyType>& kp, const WeightType& w);
pair<KeyType, KeyType> keyPair;
WeightType weight;
};

template <typename ItType> Graph(ItType lnBegin, const ItType& lnEnd);
~Graph();

VertexIt findVertex(const KeyType& k);
void dfs(const VertexIt& v, map<KeyType, bool>& visited);
void dfs();
void bfs();

list<Vertex> vertices;
list<Edge> edges;
};

#include "Graph.cpp"

#endif // GRAPH_H


Graph.cpp

#ifndef GRAPH_CPP
#define GRAPH_CPP

#include "Graph.h"
using namespace std;

template <class KeyType, class WeightType>
template <typename ItType>
Graph<KeyType, WeightType>::Graph(ItType lnBegin, const ItType& lnEnd)
{
vertices.push_back(Vertex(lnBegin->keyPair.first));

for (; lnBegin != lnEnd; ++lnBegin)
{
{
}
else
{
cout << " Skiping ";
}
cout << lnBegin->keyPair.first
<< "<-" << lnBegin->weight << "->"
<< lnBegin->keyPair.second
<< endl;
}
}

template <class KeyType, class WeightType>
Graph<KeyType, WeightType>::~Graph()
{
//dtor
}

template <class KeyType, class WeightType>
{
VertexIt fKey = findVertex(ln.keyPair.first);
VertexIt sKey = findVertex(ln.keyPair.second);
VertexIt missing = vertices.end();

if (fKey != missing || sKey != missing)
{
if (fKey == missing)
{
vertices.push_back(Vertex(ln.keyPair.first));
fKey = --vertices.end();
}
if (sKey == missing)
{
vertices.push_back(Vertex(ln.keyPair.second));
sKey = --vertices.end();
}

edges.push_back(Edge(make_pair(fKey, sKey), ln.weight));

return true;
}

return false;
}

template <class KeyType, class WeightType>
typename Graph<KeyType, WeightType>::VertexIt
Graph<KeyType, WeightType>::findVertex(const KeyType& k)
{
VertexIt it = vertices.begin();
VertexIt itEnd = vertices.end();

for (; it != itEnd; ++it)
{
if (it->key == k)
{
return it;
}
}
return itEnd;
}

template <class KeyType, class WeightType>
Graph<KeyType, WeightType>::Vertex::Vertex(const KeyType& k)
{
key = k;
}

template <class KeyType, class WeightType>
{
incEdges.push_back(e);
return true;
}

template <class KeyType, class WeightType>
Graph<KeyType, WeightType>::Edge::Edge(const pair<VertexIt, VertexIt>& vp, const WeightType& w) :
incVertices(vp), weight(w) { }

template <class KeyType, class WeightType>
keyPair(kp), weight(w) { }

template <class KeyType, class WeightType>
typename Graph<KeyType, WeightType>::VertexIt
{
if (incVertices.first == v)
{
return incVertices.second;
}
return incVertices.first;

}

template <class KeyType, class WeightType>
void Graph<KeyType, WeightType>::dfs()
{
map<KeyType, bool> visited;
dfs(vertices.begin(), visited);
}

template <class KeyType, class WeightType>
void Graph<KeyType, WeightType>::dfs(const VertexIt& v, map<KeyType, bool>& visited)
{
visited[v->key] = true;
cout << " " << v->key;

typename list<EdgeIt>::iterator it = v->incEdges.begin();
typename list<EdgeIt>::iterator itEnd = v->incEdges.end();

for (; it != itEnd; ++it)
{
if (!visited[w->key])
{
dfs(w, visited);
}
}
}

template <class KeyType, class WeightType>
void Graph<KeyType, WeightType>::bfs()
{
map<KeyType, bool> visited;
queue<VertexIt> q;

VertexIt v = vertices.begin();
q.push(v);
visited[v->key] = true;
cout << " " << v->key;

typename list<EdgeIt>::iterator it;
typename list<EdgeIt>::iterator itEnd;

while (!q.empty())
{
v = q.front();
q.pop();

it = v->incEdges.begin();
itEnd = v->incEdges.end();

for (; it != itEnd; ++it)
{
if (!visited[w->key])
{
cout << " " << w->key;
q.push(w);
visited[w->key] = true;
}
}
}
}

#endif


Test.cpp

#include <iostream>
#include "Graph.h"
using namespace std;

int main()
{
typedef Graph<char, int> Graph;

myGraph.dfs();
myGraph.bfs();

return 0;
}


Is this implementation appropriate for finding minimum spanning tree? Could it be better?, Is It a total crap?

Thanks.

-

A few tips:

• In Graph.h you #include "Graph.cpp". You should never include an implementation file.
• In Graph.h you have using namespace std. You should never bring in namespaces in a header file (except in rare cases where you put it inside some other scope), otherwise you pollute the namespaces of everyone who #includes it
• In Graph.h VertexIt findVertex(const KeyType& k) should be private, otherwise anyone can mess with the vertex list inside of Graph without going through the interface
• In Graph.cpp, you don't need include guards - these are only needed in header files
-
• You can use EdgeIt and VertexIt instead of Edge* and Vertex*
• Your algorithm might be turned into class that incrementally update MST while new links added and dropping off rest of edges that isn't improving MST.
• Consider adding lookup std::map<KeyType, Vertex> or better std::mapKeyType, Vertexes::iterator> to get faster findVertex
• Is there any reason why ctor requires const std::vector<Link> & as a source of links? You can use here any collection which you can iterate. Consider taking template iterator begin and end. That will allow you to use:
Link a[4];