strongly connected components

[ccc.git] / tarjan.c

diff --git a/tarjan.c b/tarjan.c
new file mode 100644 (file)
index 0000000..5ac7e2d
--- /dev/null
+++ b/tarjan.c
@@ -0,0 +1,131 @@
+#include <stddef.h>
+#include <stdlib.h>
+
+#include "util.h"
+
+struct edge {
+       void *from;
+       void *to;
+};
+
+struct components {
+       int nnodes;
+       void **nodes;
+       struct components *next;
+};
+
+struct node {
+       int lowlink;
+       int index;
+       bool onStack;
+       void *data;
+};
+
+static int ptrcmp(const void *l, const void *r)
+{
+       return (ptrdiff_t)((struct node *)l)->data
+               - (ptrdiff_t)((struct node *)r)->data;
+}
+
+static int nodecmp(const void *l, const void *r)
+{
+       return (ptrdiff_t)l -(ptrdiff_t)((struct node *)r)->data;
+}
+
+struct components *strongconnect(struct node *v, struct node **stack, int *sp,
+       int *index, int nedges, struct edge *edges,
+       struct components *res, struct components **tail)
+{
+       struct node *w;
+       v->index = *index;
+       v->lowlink = *index;
+       (*index)++;
+       stack[(*sp)++] = v;
+       v->onStack = true;
+
+       for (int i = 0; i<nedges; i++) {
+               //Only consider nodes reachable from v
+               if (edges[i].from != v)
+                       continue;
+               w = edges[i].to;
+               if (w->index == -1)
+                       res = strongconnect(w, stack, sp, index,
+                               nedges, edges, res, tail);
+               else if (w->onStack)
+                       v->lowlink = min(v->lowlink, w->index);
+       }
+
+       if (v->lowlink == v->index) {
+               struct components *ng = safe_malloc(sizeof(struct components));
+               if (*tail == NULL)
+                       res = ng;
+               else
+                       (*tail)->next = ng;
+               *tail = ng;
+               ng->next = NULL;
+               ng->nnodes = *sp;
+               do {
+                       w = stack[--(*sp)];
+                       w->onStack = false;
+               } while (w != v);
+               ng->nnodes -= *sp;
+               ng->nodes = safe_malloc(ng->nnodes*sizeof(void *));
+               for (int i = 0; i<ng->nnodes; i++)
+                       ng->nodes[i] = stack[*sp+i]->data;
+       }
+       return res;
+}
+
+#define nsearch(key)\
+       bsearch(key, nodes, nnodes, sizeof(struct node), nodecmp);\
+       if (key == NULL) {\
+               fprintf(stderr, "edge references unknown node\n");\
+               goto end;\
+       }\
+
+struct components *scc(int nnodes, void **nodedata, int nedges, struct edge **edgedata)
+{
+       //Create nodes
+       struct node *nodes = safe_malloc(nnodes*sizeof(struct node));
+       for (int i = 0; i<nnodes; i++)
+               nodes[i] = (struct node){.lowlink=-1, .index=-1,
+                       .onStack=false, .data=nodedata[i]};
+       qsort(nodes, nnodes, sizeof(struct node), ptrcmp);
+
+       //Create edges
+       struct edge *edges = safe_malloc(nedges*sizeof(struct edge));
+       for (int i = 0; i<nedges; i++) {
+               struct node *from = nsearch(edgedata[i]->from);
+               struct node *to = nsearch(edgedata[i]->to);
+               edges[i] = (struct edge){.from=from, .to=to};
+       }
+
+       //Tarjan's
+       struct components *res = NULL, *tail = NULL;
+       struct node **stack = safe_malloc(nnodes*sizeof(struct node *));
+       int sp = 0;
+       int index = 0;
+       for (int i = 0; i < nnodes; i++) {
+               if (nodes[i].index == -1)
+                       res = strongconnect(&nodes[i], stack, &sp, &index,
+                               nedges, edges, res, &tail);
+       }
+       free(stack);
+end:
+       free(nodes);
+       free(edges);
+       return res;
+}
+
+void components_free(struct components *cs, void (*freefun)(void *))
+{
+       while (cs != NULL) {
+               if (freefun != NULL)
+                       for (int i = 0; i<cs->nnodes; i++)
+                               freefun(cs->nodes[i]);
+               free(cs->nodes);
+               struct components *t = cs->next;
+               free(cs);
+               cs = t;
+       }
+}