Undirected, connected and weighted graph implementation

Question

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

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);
        bool addLink(const EdgeIt& e);

        list<EdgeIt> incEdges;
        KeyType key;
    };

    class Edge
    {
        friend class Graph;

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

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

    struct Link
    {
        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();

    bool addLink(const Link& ln);
    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));

    cout << " Adding links:" << endl;
    for (; lnBegin != lnEnd; ++lnBegin)
    {
        if (addLink(*lnBegin) == true)
        {
            cout << " Adding  ";
        }
        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>
bool Graph<KeyType, WeightType>::addLink(const Link& ln)
{
    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));

        fKey->addLink(--edges.end());
        sKey->addLink(--edges.end());
        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>
bool Graph<KeyType, WeightType>::Vertex::addLink(const EdgeIt& e)
{
    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>
Graph<KeyType, WeightType>::Link::Link(const pair<KeyType, KeyType>& kp, const WeightType& w) :
    keyPair(kp), weight(w) { }


template <class KeyType, class WeightType>
typename Graph<KeyType, WeightType>::VertexIt
Graph<KeyType, WeightType>::Edge::adjVertexTo(const VertexIt& v)
{
    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)
    {
        VertexIt w = (*it)->adjVertexTo(v);
        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)
        {
            VertexIt w = (*it)->adjVertexTo(v);
            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;
    typedef Graph::Link Link;

    vector<Link> links;
    links.push_back(Link(make_pair('A', 'B'), 2));
    links.push_back(Link(make_pair('A', 'C'), 2));
    links.push_back(Link(make_pair('A', 'E'), 2));
    links.push_back(Link(make_pair('B', 'D'), 7));
    links.push_back(Link(make_pair('B', 'F'), 7));
    links.push_back(Link(make_pair('C', 'G'), 7));
    links.push_back(Link(make_pair('E', 'F'), 5));

    Graph myGraph(links.begin(), links.end());
    myGraph.dfs();
    myGraph.bfs();

    return 0;
}

Is this implementation appropriate for finding minimum spanning tree? Could it be better?

Answer 1

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

Answer 2

• 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];
std::list<Link> b;
std::vector<Link> c;
Graph ga(a, a + 4);
Graph gb(b.begin(), b.end());
Graph gc(c.begin(), c.end());