tarjan.h

   1 #ifndef SCC_H
   2 #define SCC_H
   3
   4 struct edge {
   5         void *from;
   6         void *to;
   7 };
   8
   9 struct components {
  10         int nnodes;
  11         void **nodes;
  12         struct components *next;
  13 };
  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 *tarjans(int nnodes, void *nodedata[], int nedges,
  29         struct edge *edgedata[], int *error);
  30
  31 /**
  32  * Free a list of components
  33  *
  34  * @param cs components
  35  * @param freefun function to free the data with, if NULL, data isn't freed
  36  */
  37 void components_free(struct components *cs, void (*freefun)(void *));
  38
  39 #endif