BFT/DFT/Topological graph implementation

Question

I am trying to learn graphs and implement in code. Can you please review my code and give me feedback?

Source code

#include <iostream>
using namespace std;

#include <list>
#include <queue>
#include <map>

Class Edge

class Edge
{
public:
  int dest;
  int weight;

  Edge(int dest) : dest(dest), weight(0) {}
};

Class Vertex

class Vertex
{
public:
    int orig;
    std::list<Edge> adjList;
    bool visited;
    int indegree;

    Vertex() : orig(-1), visited(false), indegree(0) {}
    Vertex(int v) : orig(v), visited(false), indegree(0) {}

    friend bool operator==(const Vertex & v, int data);
    friend std::ostream & operator<<(std::ostream & os, const Vertex & v);
};

bool operator==(const Vertex & v, int data)
{
  if (v.orig == data) return true;
  return false;
}

std::ostream & operator<<(std::ostream & os, const Vertex & v)
{
  os << v.orig << ":";
  std::list<Edge>::const_iterator iter = v.adjList.begin();
  for(; iter != v.adjList.end(); ++iter)
    {
      os << " " << iter->dest;
    }

  return os;
}

Class Graph

class Graph
{
private:
    typedef std::map<int, Vertex> VertexMap;
    typedef std::map<int, Vertex>::iterator VertexIterator;
    typedef std::map<int, Vertex>::const_iterator VertexConstIterator;
    bool visit(int v, std::list<int> & sortedList);

    VertexMap vertices;
public:
    void addVertex(int v);
    void addEdge(int v1, int v2);
    void print();
    void BreadthFirstTour(int v);
    void DepthFirstTour(int v);
    void TopologicalSort();
    void resetStates();
};

void Graph::addVertex(int v) 
{
  vertices.insert( std::make_pair(v, Vertex(v)) );
}

void Graph::addEdge(int v1, int v2)
{
    VertexIterator iter = vertices.find(v1);

    if (iter != vertices.end())
    {
        Edge edge(v2);
        iter->second.adjList.push_back(edge);
    }

    iter = vertices.find(v2);
    iter->second.indegree++;
}

void Graph::print()
{
    VertexConstIterator iter = vertices.begin();
    for (; iter != vertices.end(); ++iter)
    {
        cout << iter->second << "\n";
    }
}

void Graph::BreadthFirstTour(int v)
{
  cout << "BFS BEGIN\n";

  std::queue<int> q;
  VertexConstIterator iter = vertices.find(v);
  if (iter != vertices.end())
  {
      q.push(iter->first);
  }
  else
  {
      cout << "BFS END\n";
      return;
  }

  VertexIterator iter1;
  while (!q.empty())
  {
      int vtx = q.front();
      q.pop();

      Vertex & v = vertices[vtx];
      if (v.visited == false )
      {
          v.visited = true;
          cout << v.orig << " ";

          std::list<Edge>::const_iterator iter = v.adjList.begin();
          while (iter != v.adjList.end())
            {
                //cout << "dest " << iter->dest << endl;
                VertexConstIterator citer = vertices.find(iter->dest);
                if (citer != vertices.end())
                {
                    q.push(citer->first);
                    //cout << "pushing " << citer->orig << endl;
                }
                ++iter;
            }
      }
  }

  cout << "\nBFS END" << endl;

  resetStates();
}

void Graph::resetStates()
{
    VertexIterator iter = vertices.begin();
    for (; iter != vertices.end(); ++iter)
    {
        iter->second.visited = false;
    }
}

void Graph::DepthFirstTour(int v)
{
    VertexIterator iter = vertices.find(v);
    if (iter != vertices.end())
    {
        if (iter->second.visited == false)
        {
            iter->second.visited = true;

            std::list<Edge>::iterator liter = iter->second.adjList.begin();
            for (; liter != iter->second.adjList.end(); ++liter)
            {
                DepthFirstTour(liter->dest);
            }

            cout << iter->second.orig << " ";
        }
    }
}

void Graph::TopologicalSort()
{
    VertexConstIterator iter = vertices.begin();
    std::list<int> sortedList;
    bool cycle = false;
    for (; iter != vertices.end(); ++iter)
    {
        if (iter->second.indegree == 0) 
        {
            if (!visit(iter->first, sortedList))
            {
                cycle = true;
                break;
            }
        }
    }

    if (cycle || sortedList.size() != vertices.size())
    {
        cout << "CYCLE";
        return;
    }

    std::list<int>::const_iterator liter = sortedList.begin();
    for (; liter != sortedList.end(); ++liter)
    {
        cout << *liter << " ";
    }
}

bool Graph::visit(int v, std::list<int> & sortedList)
{
    VertexIterator iter = vertices.find(v);
    if (iter != vertices.end())
    {
        if (iter->second.visited == false)
        {
            iter->second.visited = true;

            std::list<Edge>::const_iterator liter = iter->second.adjList.begin();
            for (; liter != iter->second.adjList.end(); ++liter)
            {
                if (!visit(liter->dest, sortedList))
                {
                    return false;
                }
            }
            sortedList.push_front(iter->first);
        }
        else
        {
            return false;
        }
    }
    return true;
}

main()

int main()
{
    Graph g;

    g.addVertex(1);
    g.addVertex(2);
    g.addVertex(3);
    g.addVertex(4);
    g.addVertex(5);
    g.addVertex(6);
    g.addVertex(7);
    g.addVertex(8);

    g.addEdge(1,2);
    g.addEdge(1,3);
    g.addEdge(2,4);
    g.addEdge(2,5);
    g.addEdge(3,6);
    g.addEdge(3,7);
    //g.addEdge(5,8); //disjoint node 8

    //g.addEdge(6,3); //this is forming cycle

    g.print();

    g.BreadthFirstTour(1);

    cout << "DFS START\n";
    g.DepthFirstTour(1);
    g.resetStates();
    cout << "\nDFS END" << endl;

    cout << "TOPOLOGICAL SORT START\n";
    g.TopologicalSort();
    g.resetStates();
    cout << "\nTOPOLOGICAL SORT END\n";

    return 0;
}

Answer 1

Don't put using namespace std
before including other header files
If you must do it then put it after all the includes. But preferably don't use it at all.

#include <iostream>
using namespace std;

#include <list>
#include <queue>
#include <map>

Do you really want all the members of Vertix to be public?

public:
int orig;
std::list<Edge> adjList;
bool visited;
int indegree;

Equality test is correct:

if (v.orig == data) return true;
return false;

But it is easier to read when written like this:

return v.orig == data;

When you have an operator << it is usually a good idea to implement >> (in the long run you probably will). Thus when writing your output stream you want to write it in a way that makes reading it back in easy. So when you class contains things like vectors it is useful to prefix them with a count of elements (not a termination marker). Also any sub elements should be printed with their own stream operator << so you should probably write one for Edge as well.

Typedef the iterators in terms of the container. That way if you change the container you only need to make one change (not a cascade of changes).

typedef std::map<int, Vertex> VertexMap;
typedef std::map<int, Vertex>::iterator VertexIterator;
typedef std::map<int, Vertex>::const_iterator VertexConstIterator;

could be written as:

typedef std::map<int, Vertex>     VertexMap;
typedef VertexMap::iterator       VertexIterator;
typedef VertexMap::const_iterator VertexConstIterator;
     // ^^^^^^^^^  Use the container type we just defined.

Here is where you public members are going to haunt you.

    iter->second.adjList.push_back(edge);

You are binding your representation of a vertices to always contain its list of edges in this manor. You should really define a more abstract interface on the class that will allow you to change the internal representations without affecting the implementation of Graph.

When you add edges to a graph.
You check that the source is there. But you do not check that a destination node has been created. I would expect this to be more symmetrical.

Is the method 'void resetStates()' really a member of the public interface?

In your BreadthFirstTour/DepthFirstTour traversal of the graph. Its not really a breadth first/Depth first tour (as this implies a breadth or depth) while a graph is bit less symmetric than that (especially since edges have a weight and the graph may not be fully connected).

But as part of the implementation you actually store whether a node (vertex) has been visited as a member of the vertex. You are basically tightly coupling the traversal of the graph to its implementation which may restrict you in future enhancements to the graph (and limiting how the graph can be traversed).

You can de-couple how the graph is traversed from the implementation of the graph by using a visitor pattern. This also conforms to the open/closed principle by making your class open to expansion but closed to change by allowing the traversal mechanism to be specified externally to the graph.