scc.c

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