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