tarjan.c

   1 #include <stddef.h>
   2 #include <stdlib.h>
   3 #include <stdbool.h>
   4
   5 #ifndef min
   6 #define min(x, y) ((x)<(y) ? (x) : (y))
   7 #endif
   8
   9 struct edge {
  10         void *from;
  11         void *to;
  12 };
  13
  14 struct components {
  15         int nnodes;
  16         void **nodes;
  17         struct components *next;
  18 };
  19
  20 struct node {
  21         int index;
  22         int lowlink;
  23         bool onStack;
  24         void *data;
  25 };
  26
  27 struct tjstate {
  28         int index;
  29         int sp;
  30         int nedges;
  31         struct edge *edges;
  32         struct node **stack;
  33         struct components *head;
  34         struct components *tail;
  35 };
  36
  37 static int nodecmp(const void *l, const void *r)
  38 {
  39         return (ptrdiff_t)l -(ptrdiff_t)((struct node *)r)->data;
  40 }
  41
  42 static int strongconnect(struct node *v, struct tjstate *tj)
  43 {
  44         struct node *w;
  45
  46         /* Set the depth index for v to the smallest unused index */
  47         v->index = tj->index;
  48         v->lowlink = tj->index;
  49         tj->index++;
  50         tj->stack[tj->sp] = v;
  51         tj->sp++;
  52         v->onStack = true;
  53
  54         for (int i = 0; i<tj->nedges; i++) {
  55                 /* Only consider nodes reachable from v */
  56                 if (tj->edges[i].from != v) {
  57                         continue;
  58                 }
  59                 w = tj->edges[i].to;
  60                 /* Successor w has not yet been visited; recurse on it */
  61                 if (w->index == -1) {
  62                         int r = strongconnect(w, tj);
  63                         if (r != 0)
  64                                 return r;
  65                         v->lowlink = min(v->lowlink, w->lowlink);
  66                 /* Successor w is in stack S and hence in the current SCC */
  67                 } else if (w->onStack) {
  68                         v->lowlink = min(v->lowlink, w->index);
  69                 }
  70         }
  71
  72         /* If v is a root node, pop the stack and generate an SCC */
  73         if (v->lowlink == v->index) {
  74                 struct components *ng = malloc(sizeof(struct components));
  75                 if (ng == NULL) {
  76                         return 2;
  77                 }
  78                 if (tj->tail == NULL) {
  79                         tj->head = ng;
  80                 } else {
  81                         tj->tail->next = ng;
  82                 }
  83                 tj->tail = ng;
  84                 ng->next = NULL;
  85                 ng->nnodes = 0;
  86                 do {
  87                         tj->sp--;
  88                         w = tj->stack[tj->sp];
  89                         w->onStack = false;
  90                         ng->nnodes++;
  91                 } while (w != v);
  92                 ng->nodes = malloc(ng->nnodes*sizeof(void *));
  93                 if (ng == NULL) {
  94                         return 2;
  95                 }
  96                 for (int i = 0; i<ng->nnodes; i++) {
  97                         ng->nodes[i] = tj->stack[tj->sp+i]->data;
  98                 }
  99         }
 100         return 0;
 101 }
 102
 103 static int ptrcmp(const void *l, const void *r)
 104 {
 105         return (ptrdiff_t)((struct node *)l)->data
 106                 - (ptrdiff_t)((struct node *)r)->data;
 107 }
 108
 109 /**
 110  * Calculate the strongly connected components using Tarjan's algorithm:
 111  * en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
 112  *
 113  * Returns NULL when there are invalid edges and sets the error to:
 114  * 1 if there was a malformed edge
 115  * 2 if malloc failed
 116  *
 117  * @param number of nodes
 118  * @param data of the nodes
 119  * @param number of edges
 120  * @param data of edges
 121  * @param pointer to error code
 122  */
 123 struct components *tarjans(
 124                 int nnodes, void *nodedata[],
 125                 int nedges, struct edge *edgedata[],
 126                 int *error)
 127 {
 128         struct node nodes[nnodes];
 129         struct edge edges[nedges];
 130         struct node *stack[nnodes];
 131         struct node *from, *to;
 132         struct tjstate tj = {0, 0, nedges, edges, stack, NULL, .tail=NULL};
 133
 134         // Populate the nodes
 135         for (int i = 0; i<nnodes; i++) {
 136                 nodes[i] = (struct node){-1, -1, false, nodedata[i]};
 137         }
 138         qsort(nodes, nnodes, sizeof(struct node), ptrcmp);
 139
 140         // Populate the edges
 141         for (int i = 0; i<nedges; i++) {
 142                 from = bsearch(edgedata[i]->from, nodes, nnodes,
 143                         sizeof(struct node), nodecmp);
 144                 if (from == NULL) {
 145                         *error = 1;
 146                         return NULL;
 147                 }
 148                 to = bsearch(edgedata[i]->to, nodes, nnodes,
 149                         sizeof(struct node), nodecmp);
 150                 if (to == NULL) {
 151                         *error = 1;
 152                         return NULL;
 153                 }
 154                 edges[i] = (struct edge){.from=from, .to=to};
 155         }
 156
 157         //Tarjan's
 158         for (int i = 0; i < nnodes; i++) {
 159                 if (nodes[i].index == -1) {
 160                         *error = strongconnect(&nodes[i], &tj);
 161                         if (*error != 0)
 162                                 return NULL;
 163                 }
 164         }
 165         return tj.head;
 166 }
 167
 168 void components_free(struct components *cs, void (*freefun)(void *))
 169 {
 170         struct components *t;
 171
 172         while (cs != NULL) {
 173                 if (freefun != NULL) {
 174                         for (int i = 0; i<cs->nnodes; i++) {
 175                                 freefun(cs->nodes[i]);
 176                         }
 177                 }
 178                 free(cs->nodes);
 179                 t = cs->next;
 180                 free(cs);
 181                 cs = t;
 182         }
 183 }