# [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:

- Connection Matrix
- 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.

More Related questions

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.