Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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);
        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?, Is It a total crap?

Thanks.

share|improve this question
add comment

2 Answers 2

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
share|improve this answer
add comment
  • 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());
share|improve this answer
    
Hi, thanks for the advices, I modified my code a little. –  joseljmz Jan 16 '13 at 22:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.