BFT/DFT/Topological graph implementation

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

Source code

#include 
using namespace std;

#include 
#include 
#include 

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 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::const_iterator iter = v.adjList.begin();
  for(; iter != v.adjList.end(); ++iter)
    {
      os dest;
    }

  return os;
}

Class Graph

```
class Graph
{
private:
typedef std::map VertexMap;
typedef std::map::iterator VertexIterator;
typedef std::map::const_iterator VertexConstIterator;
bool visit(int v, std::list & 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 second q;
VertexConstIterator iter = vertices.find(v);
if (iter != vertices.end())
{
q.push(iter->first);
}
else
{
cout ::const_iterator iter = v.adjList.begin();
while (iter != v.adjList.end())
{
//cout dest dest);
if (citer

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 
using namespace std;

#include 
#include 
#include 

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

public:
int orig;
std::list 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 > (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 VertexMap;
typedef std::map::iterator VertexIterator;
typedef std::map::const_iterator VertexConstIterator;

could be written as:

typedef std::map     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.

StackExchange Code Review Q#4561, answer score: 2