Directed graph implementation

Question

I need to implement a digraph(Directed graph) in c++ as part of a homework and I'm having some issues with how to represent the vertices and edges data types.
Can anybody please point me to a example or a simple c++ class that implements this so I can study it and extend from there?

I've googled for a bit but I only found results about using Boost or other libraries, I just need something simple that doesn't rely on any library.

Thank you.

Answer 1

There are two major ways of representing digraphs with data structures:

Node centric. This method represents each node as an object within your program, and each node contains information about other nodes it links to. The other nodes can be as simple as a list of nodes where there exists a directed edge between the current node and the target node.

Edge centric. This method represents each edge as an object within your program, and each edge contains information about which nodes it connects. In a digraph, each edge will have exactly one "source" and "destination" node (which may be the same node if you're considering self-loops). This method is essentially a list of ordered pairs.

Depending on the problem you're solving, one of these two basic forms will end up being most appropriate. More specific algorithms might need to add more information to the above basic structures, such as for example a list of all nodes reachable from the current node.

Answer 2

Loosely, there are 2 straightforward ways of representing graphs:

1. Connection Matrix
2. List of Lists.

Each has advantages/disadvantages, depending on the application.

#2 will involve a lot of pointer fiddling.

#1 is often easier to use when doing graph transformationss.

In either one, you're going to have something like this:

template<typename T>
class node
{
   public:
   T data;
};

And the matrix and list of list classes will be pointing to dynamically allocated node's.

The implication is that you will have a graph class and a node class.

Answer 3

Try a vector< NodeType > with a multimap< NodeType *, EdgeType>.

multimap doesn't support subscripting [ x ] so you'll need to use edges.lower_bound() instead.

Alternatively, a map< pair< NodeType *, NodeType * >, EdgeType > can help look for an edge given two nodes. I used exactly that in one pretty heavy-duty program.

Here's an example for the first suggestion:

struct NodeType {
    int distance;
    NodeType( int d ) { distance = d; }
};
struct EdgeType  {
    int weight;
    NodeType *link;
    EdgeType( int w, NodeType *l ) { weight = w; link = l }
};

vector< NodeType > nodes;
nodes.reserve( 3 );
nodes.push_back( NodeType( 0 ) );
nodes.push_back( NodeType( 0 ) );
nodes.push_back( NodeType( 0 ) );

multimap< NodeType *, EdgeType > edges;
edges.insert( make_pair( &nodes[0], EdgeType( 4, &nodes[2] ) ) );
edges.insert( make_pair( &nodes[0], EdgeType( 1, &nodes[1] ) ) );
edges.insert( make_pair( &nodes[2], EdgeType( 2, &nodes[0] ) ) );

for ( multimap< NodeType *, EdgeType >::iterator iter = edges.lower_bound( &nodes[1] ),
  end = edges.upper_bound( &nodes[1] ); iter != end; ++ iter ) {
    cerr << "1 connects to " << iter->second.link - nodes.begin() << endl;
}