Directional chart implementation

Question

I need to implement a Directed graph in C ++ as part of my homework, and I am having some problems with representing data types of vertices and edges.
Can someone point me to an example or a simple C ++ class that implements this so that I can study it and continue from there?

I searched Google 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.

Thanks.

Answer 1

There are two main ways to represent digraphs with data structures:

Node oriented . This method represents each node as an object inside your program, and each node contains information about the other nodes to which it is attached. Other nodes can be as simple as a list of nodes where there is a directed edge between the current node and the target node.

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

Depending on the problem you are solving, one of these two basic forms will be most appropriate. More specific algorithms may need to add additional information to the above basic structures, such as, for example, a list of all nodes available from the current node.

Answer 2

Wrong, there are two easy ways to present graphs:

• Compound Matrix
• List of lists.

Each has advantages / disadvantages, depending on the application.

# 2 will include many pointers.

# 1 is often easier to use when performing graph transformations.

In one of them you will have something like this:

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

Both the matrix and the list of list classes will point to dynamically allocated node .

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

Answer 3

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

multimap does not support indexing [ x ] , so you will need to use edges.lower_bound() .

Alternatively, map< pair< NodeType *, NodeType * >, EdgeType > can help find the edge given by two nodes. I used exactly this in one rather heavy program.

Here is an example of the first sentence:

 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; } 

Answer 4

This university document can help you.

This is not the most complete, but perhaps it gives you an idea. I found this very useful, it is also for a lecture, so there is no risk of copying anything that should not be.

Answer 5

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

Most likely, you will also want to save the list<node<dataType>*> all nodes.