scc.h

   1 #ifndef SCC_H
   2 #define SCC_H
   3
   4 #include <stdbool.h>
   5 struct edge {
   6         void *from;
   7         void *to;
   8 };
   9
  10 struct components {
  11         int nnodes;
  12         void **nodes;
  13         struct components *next;
  14 };
  15 #define FOREACHCOMP(x, l) for(struct components *x = l; x != NULL; x = x->next)
  16
  17 /**
  18  * Calculate the strongly connected components using Tarjan's algorithm:
  19  * en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
  20  *
  21  * Returns NULL when there are invalid edges
  22  *
  23  * @param number of nodes
  24  * @param data of the nodes
  25  * @param number of edges
  26  * @param data of edges
  27  */
  28 struct components *scc(int nnodes, void **nodedata, int nedges, struct edge *edgedata);
  29
  30 /**
  31  * Free a list of components
  32  *
  33  * @param cs components
  34  * @param freefun function to free the data with, if NULL, data isn't freed
  35  */
  36 void components_free(struct components *cs, void (*free)(void *));
  37
  38 #endif