Graph implementation C++

Question

I was wondering about a quick to write implementation of a graph in c++. I need the data structure to be easy to manipulate and use graph algorithms(such as BFS,DFS, Kruskal, Dijkstra...). I need this implementation for an algorithms Olympiad, so the easier to write the data structure the better.

Can you suggest such DS(main structs or classes and what will be in them). I know that an Adjacency list and Adjacency matrix are the main possibilities, but I mean a more detailed code sample.

For example I thought about this DS last time I had to implement a graph for DFS:

struct Edge {   int start;   int end;   struct Edge* nextEdge; } 

and then used a array of size n containing in its i'th place the Edge List(struct Edge) representing the edges starting in the i'th node.

but when trying to DFS on this graph I had to write a 50 line code with about 10 while loops.

What 'good' implementations are there?

Answer 1

Below is a implementation of Graph Data Structure in C++ as Adjacency List.

I have used STL vector for representation of vertices and STL pair for denoting edge and destination vertex.

#include <iostream> #include <vector> #include <map> #include <string>  using namespace std;  struct vertex {     typedef pair<int, vertex*> ve;     vector<ve> adj; //cost of edge, destination vertex     string name;     vertex(string s) : name(s) {} };  class graph { public:     typedef map<string, vertex *> vmap;     vmap work;     void addvertex(const string&);     void addedge(const string& from, const string& to, double cost); };  void graph::addvertex(const string &name) {     vmap::iterator itr = work.find(name);     if (itr == work.end())     {         vertex *v;         v = new vertex(name);         work[name] = v;         return;     }     cout << "\nVertex already exists!"; }  void graph::addedge(const string& from, const string& to, double cost) {     vertex *f = (work.find(from)->second);     vertex *t = (work.find(to)->second);     pair<int, vertex *> edge = make_pair(cost, t);     f->adj.push_back(edge); } 

Answer 2

It really depends on what algorithms you need to implement, there is no silver bullet (and that's shouldn't be a surprise... the general rule about programming is that there's no general rule ;-) ).

I often end up representing directed multigraphs using node/edge structures with pointers... more specifically:

struct Node {     ... payload ...     Link *first_in, *last_in, *first_out, *last_out; };  struct Link {     ... payload ...     Node *from, *to;     Link *prev_same_from, *next_same_from,          *prev_same_to, *next_same_to; }; 

In other words each node has a doubly-linked list of incoming links and a doubly-linked list of outgoing links. Each link knows from and to nodes and is at the same time in two different doubly-linked lists: the list of all links coming out from the same from node and the list of all links arriving at the same to node.

The pointers prev_same_from and next_same_from are used when following the chain of all the links coming out from the same node; the pointers prev_same_to and next_same_to are instead used when managing the chain of all the links pointing to the same node.

It's a lot of pointer twiddling (so unless you love pointers just forget about this) but query and update operations are efficient; for example adding a node or a link is O(1), removing a link is O(1) and removing a node x is O(deg(x)).

Of course depending on the problem, payload size, graph size, graph density this approach can be way overkilling or too much demanding for memory (in addition to payload you've 4 pointers per node and 6 pointers per link).

A similar structure full implementation can be found here.