[ACCEPTED]-Directed graph implementation-graph

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

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

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

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

Loosely, there are 2 straightforward ways 9 of representing graphs:

1. Connection Matrix
2. List of Lists.

Each has advantages/disadvantages, depending 8 on the application.

#2 will involve a lot 7 of pointer fiddling.

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

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

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

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

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

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

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

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

Here's an example for the first 1 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;
}

This university paper might help you.

It's not the most complete, but 4 it gives you an idea perhaps. I found it 3 rather useful, it's also for a lecture so 2 there is no risk of copying anything one 1 shouldn't.

template<class T>
class node
{
public:
    T data;
    vector<node<T>*> edges;
}

You will most likely also want to store 1 a list<node<dataType>*> of all the nodes.