tarjan.c

   1 #include <stddef.h>
   2 #include <stdlib.h>
   3
   4 #include "util.h"
   5
   6 struct edge {
   7         void *from;
   8         void *to;
   9 };
  10
  11 struct components {
  12         int nnodes;
  13         void **nodes;
  14         struct components *next;
  15 };
  16
  17 struct node {
  18         int lowlink;
  19         int index;
  20         bool onStack;
  21         void *data;
  22 };
  23
  24 static int ptrcmp(const void *l, const void *r)
  25 {
  26         return (ptrdiff_t)((struct node *)l)->data
  27                 - (ptrdiff_t)((struct node *)r)->data;
  28 }
  29
  30 static int nodecmp(const void *l, const void *r)
  31 {
  32         return (ptrdiff_t)l -(ptrdiff_t)((struct node *)r)->data;
  33 }
  34
  35 struct components *strongconnect(struct node *v, struct node **stack, int *sp,
  36         int *index, int nedges, struct edge *edges,
  37         struct components *res, struct components **tail)
  38 {
  39         struct node *w;
  40         v->index = *index;
  41         v->lowlink = *index;
  42         (*index)++;
  43         stack[(*sp)++] = v;
  44         v->onStack = true;
  45
  46         for (int i = 0; i<nedges; i++) {
  47                 //Only consider nodes reachable from v
  48                 if (edges[i].from != v)
  49                         continue;
  50                 w = edges[i].to;
  51                 if (w->index == -1)
  52                         res = strongconnect(w, stack, sp, index,
  53                                 nedges, edges, res, tail);
  54                 else if (w->onStack)
  55                         v->lowlink = min(v->lowlink, w->index);
  56         }
  57
  58         if (v->lowlink == v->index) {
  59                 struct components *ng = safe_malloc(sizeof(struct components));
  60                 if (*tail == NULL)
  61                         res = ng;
  62                 else
  63                         (*tail)->next = ng;
  64                 *tail = ng;
  65                 ng->next = NULL;
  66                 ng->nnodes = *sp;
  67                 do {
  68                         w = stack[--(*sp)];
  69                         w->onStack = false;
  70                 } while (w != v);
  71                 ng->nnodes -= *sp;
  72                 ng->nodes = safe_malloc(ng->nnodes*sizeof(void *));
  73                 for (int i = 0; i<ng->nnodes; i++)
  74                         ng->nodes[i] = stack[*sp+i]->data;
  75         }
  76         return res;
  77 }
  78
  79 #define nsearch(key)\
  80         bsearch(key, nodes, nnodes, sizeof(struct node), nodecmp);\
  81         if (key == NULL) {\
  82                 fprintf(stderr, "edge references unknown node\n");\
  83                 goto end;\
  84         }\
  85
  86 struct components *scc(int nnodes, void **nodedata, int nedges, struct edge **edgedata)
  87 {
  88         //Create nodes
  89         struct node *nodes = safe_malloc(nnodes*sizeof(struct node));
  90         for (int i = 0; i<nnodes; i++)
  91                 nodes[i] = (struct node){.lowlink=-1, .index=-1,
  92                         .onStack=false, .data=nodedata[i]};
  93         qsort(nodes, nnodes, sizeof(struct node), ptrcmp);
  94
  95         //Create edges
  96         struct edge *edges = safe_malloc(nedges*sizeof(struct edge));
  97         for (int i = 0; i<nedges; i++) {
  98                 struct node *from = nsearch(edgedata[i]->from);
  99                 struct node *to = nsearch(edgedata[i]->to);
 100                 edges[i] = (struct edge){.from=from, .to=to};
 101         }
 102
 103         //Tarjan's
 104         struct components *res = NULL, *tail = NULL;
 105         struct node **stack = safe_malloc(nnodes*sizeof(struct node *));
 106         int sp = 0;
 107         int index = 0;
 108         for (int i = 0; i < nnodes; i++) {
 109                 if (nodes[i].index == -1)
 110                         res = strongconnect(&nodes[i], stack, &sp, &index,
 111                                 nedges, edges, res, &tail);
 112         }
 113         free(stack);
 114 end:
 115         free(nodes);
 116         free(edges);
 117         return res;
 118 }
 119
 120 void components_free(struct components *cs, void (*freefun)(void *))
 121 {
 122         while (cs != NULL) {
 123                 if (freefun != NULL)
 124                         for (int i = 0; i<cs->nnodes; i++)
 125                                 freefun(cs->nodes[i]);
 126                 free(cs->nodes);
 127                 struct components *t = cs->next;
 128                 free(cs);
 129                 cs = t;
 130         }
 131 }