# [ACCEPTED]-Directed graph implementation-graph

Score: 31

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.

Score: 3

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

1. Connection Matrix
2. List of Lists.

#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.

Score: 2

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;
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, EdgeType( 4, &nodes ) ) );
edges.insert( make_pair( &nodes, EdgeType( 1, &nodes ) ) );
edges.insert( make_pair( &nodes, EdgeType( 2, &nodes ) ) );

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

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.

Score: 0
``````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.

More Related questions