add scc and update other code

[ccc.git] / scc.c

diff --git a/scc.c b/scc.c
new file mode 100644 (file)
index 0000000..3c690a2
--- /dev/null
+++ b/scc.c
@@ -0,0 +1,135 @@
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#include "list.h"
+#include "util.h"
+#include "scc.h"
+
+struct node {
+       int lowlink;
+       int index;
+       bool onStack;
+       void *data;
+};
+
+struct edge2 {
+       struct node *from;
+       struct node *to;
+};
+
+int ptrcmp(const void *l, const void *r)
+{
+       return ((ptrdiff_t)((struct node *)l)->data)
+               -((ptrdiff_t)((struct node *)r)->data);
+}
+
+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 edge2 *edges, struct components *components)
+{
+       struct node *w;
+       v->index = *index;
+       v->lowlink = *index;
+       (*index)++;
+       stack[(*sp)++] = v;
+       v->onStack = true;
+
+       for (int i = 0; i<nedges; i++) {
+               if (edges[i].from != v)
+                       continue;
+               w = edges[i].to;
+               if (w->index == -1) {
+                       components = strongconnect(w, stack, sp, index,
+                               nedges, edges, components);
+               } else if (w->onStack) {
+                       v->lowlink = min(v->lowlink, w->index);
+               }
+       }
+
+       if (v->lowlink == v->index) {
+               struct list *res = NULL;
+               do {
+                       w = stack[--*sp];
+                       w->onStack = false;
+                       res = list_cons(w->data, res);
+               } while (w != v);
+               struct components *ng = safe_malloc(sizeof(struct components));
+               ng->next = components;
+               ng->nodes = list_to_array(res, &ng->nnodes, false);
+               components = ng;
+       }
+       return components;
+}
+
+struct components *scc(int nnodes, void **nodedata, int nedges, struct edge *edgedata)
+{
+       struct components *res = NULL;
+       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);
+
+       struct edge2 *edges = safe_malloc(nedges*sizeof(struct edge2));
+       for (int i = 0; i<nedges; i++) {
+               struct node *from = bsearch(edgedata[i].from, nodes, nnodes,
+                       sizeof(struct node), nodecmp);
+               if (from == NULL) {
+                       fprintf(stderr, "edge from references unknown node\n");
+                       goto end;
+               }
+               struct node *to = bsearch(edgedata[i].to, nodes, nnodes,
+                       sizeof(struct node), nodecmp);
+               if (to == NULL) {
+                       fprintf(stderr, "edge to references unknown node\n");
+                       goto end;
+               }
+               edges[i] = (struct edge2){.from=from, .to=to};
+       }
+
+       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);
+end:
+       free(stack);
+       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;
+       }
+}
+//
+//int main ()
+//{
+//     void *nodes[] = {(void *)1, (void *)2, (void *)3};
+//     struct edge edges[] = {{(void *)1, (void *)2}, {(void *)2, (void *)1}};
+//     struct components *cs = scc(3, &nodes[0], 2, &edges[0]);
+//     FOREACHCOMP(c, cs) {
+//             fprintf(stderr, "comp: ");
+//             for (int i = 0; i<c->nnodes; i++)
+//                     fprintf(stderr, "%d, ", c->nodes[i]);
+//             fprintf(stderr, "\n");
+//     }
+//     components_free(cs, NULL);
+//}