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

User · Accepted Answer

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.

User · Answer

The most common representations are probably these two    Adjacency list Adjacency matrix   Of these two the adjacency matrix is the simplest  as long as you don t mind having a  possibly huge  n   n array  where n is the number of vertices  Depending on the base type of the array  you can even store edge weights for use in e g  shortest path discovery algorithms

User · Answer

I prefer using an adjacency list of Indices   not pointers     typedef std  vector lt  Vertex  gt  Vertices  typedef std  set  lt int gt  Neighbours    struct Vertex   private     int data  public     Neighbours neighbours      Vertex  int d    data d        Vertex     data -1         bool operator lt   const Vertex amp  ref   const         return   ref data  lt  data            bool operator    const Vertex amp  ref   const         return   ref data    data             class Graph   private      Vertices vertices     void Graph  addEdgeIndices   int index1  int index2       vertices  index1   neighbours insert  index2        Vertices  iterator Graph  findVertexIndex  int val  bool amp  res        std  vector lt Vertex gt   iterator it     Vertex v val      it   std  find  vertices begin    vertices end    v       if  it    vertices end             res   true         return it       else          res   false         return vertices end            void Graph  addEdge   int n1  int n2         bool foundNet1   false  foundNet2   false     Vertices  iterator vit1   findVertexIndex  n1  foundNet1       int node1Index   -1  node2Index   -1     if    foundNet1           Vertex v1  n1          vertices push back  v1          node1Index   vertices size   - 1       else         node1Index   vit1 - vertices begin            Vertices  iterator vit2   findVertexIndex  n2  foundNet2      if    foundNet2           Vertex v2  n2          vertices push back  v2          node2Index   vertices size   - 1       else         node2Index   vit2 - vertices begin             assert    node1Index  gt  -1    amp  amp    node1Index  lt   vertices size         assert    node2Index  gt  -1    amp  amp    node2Index  lt   vertices size          addEdgeIndices  node1Index  node2Index

User · Answer

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  lt iostream gt   include  lt vector gt   include  lt map gt   include  lt string gt   using namespace std   struct vertex       typedef pair lt int  vertex  gt  ve      vector lt ve gt  adj    cost of edge  destination vertex     string name      vertex string s    name s         class graph   public      typedef map lt string  vertex   gt  vmap      vmap work      void addvertex const string amp        void addedge const string amp  from  const string amp  to  double cost       void graph  addvertex const string  amp name        vmap  iterator itr   work find name       if  itr    work end                  vertex  v          v   new vertex name           work name    v          return            cout  lt  lt    nVertex already exists       void graph  addedge const string amp  from  const string amp  to  double cost        vertex  f    work find from - gt second       vertex  t    work find to - gt second       pair lt int  vertex   gt  edge   make pair cost  t       f- gt adj push back edge

User · Answer

This question is ancient but for some reason I can t seem to get it out of my mind   While all of the solutions do provide an implementation of graphs  they are also all very verbose  They are simply not elegant   Instead of inventing your own graph class all you really need is a way to tell that one point is connected to another -- for that  std  map and std  unordered map work perfectly fine  Simply  define a graph as a map between nodes and lists of edges  If you don t need extra data on the edge  a list of end nodes will do just fine   Thus a succinct graph in C    could be implemented like so    using graph   std  map lt int  std  vector lt int gt  gt     Or  if you need additional data   struct edge       int nodes 2       float cost     add more if you need it     using graph   std  map lt int  std  vector lt edge gt  gt     Now your graph structure will plug nicely into the rest of the language and you don t have to remember any new clunky interface -- the old clunky interface will do just fine   No benchmarks  but I have a feeling this will also outperform the other suggestions here   NB  the ints are not indices -- they are identifiers

User · Answer

Here is a basic implementation of a graph   Note  I use vertex which is chained to next vertex  And each vertex has a list pointing to adjacent nodes     include  lt iostream gt  using namespace std       1 - gt 2     1- gt 4    2 - gt 3    4- gt 3    4 - gt  5    Adjacency list    1- gt 2- gt 3-null    2- gt 3- gt null   4- gt 5- gt null      Structure of a vertex struct vertex      int i     struct node  list     struct vertex  next     typedef struct vertex   VPTR      Struct of adjacency list struct node       struct vertex   n      struct node  next      typedef struct node   NODEPTR   class Graph       public             list of nodes chained together         VPTR V          Graph                 V   NULL                    void addEdge int  int           VPTR  addVertex int           VPTR existVertex int i           void listVertex           If vertex exist  it returns its pointer else returns NULL VPTR Graph  existVertex int i        VPTR temp    V      while temp    NULL            if temp- gt i    i                return temp                    temp   temp- gt next           return NULL       Add a new vertex to the end of the vertex list VPTR Graph  addVertex int i        VPTR temp   new struct vertex       temp- gt list   NULL      temp- gt i   i      temp- gt next   NULL       VPTR  curr    amp V      while  curr            curr    amp   curr - gt next             curr   temp      return temp        Add a node from vertex i to j      first check if i and j exists  If not first add the vertex    and then add entry of j into adjacency list of i void Graph  addEdge int i  int j         VPTR v i   existVertex i          VPTR v j   existVertex j          if v i    NULL            v i   addVertex i             if v j    NULL            v j   addVertex j              NODEPTR  temp    amp  v i- gt list       while  temp            temp    amp   temp - gt next             temp   new struct node         temp - gt n   v j        temp - gt next   NULL       List all the vertex  void Graph  listVertex         VPTR temp   V      while temp            cout  lt  lt temp- gt i  lt  lt              temp   temp- gt next            cout  lt  lt   n          Client program int main         Graph G      G addEdge 1  2       G listVertex         With the above code  you can expand to do DFS BFS etc

User · Answer

There can be an even simpler representation assuming that one has to only test graph algorithms not use them graph  else where  This can be as a map from vertices to their adjacency lists as shown below  -   include lt bits stdc   h gt  using namespace std      implement the graph as a map from the integer index as a key to the   adjacency list    of the graph implemented as a vector being the value of each individual key  The    program will be given a matrix of numbers  the first element of each row will    represent the head of the adjacency list and the rest of the elements will be the    list of that element in the graph      typedef map lt int  vector lt int gt   gt  graphType   int main     graphType graph  int vertices   0   cout  lt  lt   Please enter the number of vertices in the graph  -    lt  lt  endl  cin  gt  gt  vertices  if vertices  lt   0       cout  lt  lt   The number of vertices in the graph can t be less than or equal to 0    lt  lt  endl      exit 0      cout  lt  lt   Please enter the elements of the graph  as an adjacency list  one row after another     lt  lt  endl  for int i   0  i  lt   vertices  i          vector lt int gt  adjList                       the vector corresponding to the adjacency list of each vertex      int key   -1  listValue   -1      string listString      getline cin  listString       if i    0           istringstream iss listString           iss  gt  gt  key          iss  gt  gt  listValue          if listValue    -1               adjList push back listValue               for   iss  gt  gt  listValue                     adjList push back listValue                             graph insert graphType  value type key  adjList                      else             graph insert graphType  value type key  adjList               print the elements of the graph cout  lt  lt   The graph that you entered  -    lt  lt  endl  for graphType  const iterator iterator   graph begin    iterator    graph end      iterator       cout  lt  lt   Key      lt  lt  iterator- gt first  lt  lt     values           vector lt int gt   const iterator vectBegIter   iterator- gt second begin        vector lt int gt   const iterator vectEndIter   iterator- gt second end        for   vectBegIter    vectEndIter    vectBegIter           cout  lt  lt    vectBegIter   lt  lt                  cout  lt  lt  endl

[c++] Graph implementation C++

Examples related to c++

Examples related to graph