isl_tarjan.c

   1 /*
   2  * Copyright 2010-2011 INRIA Saclay
   3  * Copyright 2012      Ecole Normale Superieure
   4  *
   5  * Use of this software is governed by the MIT license
   6  *
   7  * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
   8  * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
   9  * 91893 Orsay, France
  10  * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
  11  */
  12
  13 #include <stdlib.h>
  14 #include <isl/ctx.h>
  15 #include <isl_tarjan.h>
  16
  17 void isl_tarjan_graph_free(struct isl_tarjan_graph *g)
  18 {
  19         if (!g)
  20                 return;
  21         free(g->node);
  22         free(g->stack);
  23         free(g->order);
  24         free(g);
  25 }
  26
  27 static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)
  28 {
  29         struct isl_tarjan_graph *g;
  30         int i;
  31
  32         g = isl_calloc_type(ctx, struct isl_tarjan_graph);
  33         if (!g)
  34                 return NULL;
  35         g->len = len;
  36         g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);
  37         if (!g->node)
  38                 goto error;
  39         for (i = 0; i < len; ++i)
  40                 g->node[i].index = -1;
  41         g->stack = isl_alloc_array(ctx, int, len);
  42         if (!g->stack)
  43                 goto error;
  44         g->order = isl_alloc_array(ctx, int, 2 * len);
  45         if (!g->order)
  46                 goto error;
  47
  48         g->sp = 0;
  49         g->index = 0;
  50         g->op = 0;
  51
  52         return g;
  53 error:
  54         isl_tarjan_graph_free(g);
  55         return NULL;
  56 }
  57
  58 /* Perform Tarjan's algorithm for computing the strongly connected components
  59  * in the graph with g->len nodes and with edges defined by "follows".
  60  */
  61 static int isl_tarjan_components(struct isl_tarjan_graph *g, int i,
  62         int (*follows)(int i, int j, void *user), void *user)
  63 {
  64         int j;
  65
  66         g->node[i].index = g->index;
  67         g->node[i].min_index = g->index;
  68         g->node[i].on_stack = 1;
  69         g->index++;
  70         g->stack[g->sp++] = i;
  71
  72         for (j = g->len - 1; j >= 0; --j) {
  73                 int f;
  74
  75                 if (j == i)
  76                         continue;
  77                 if (g->node[j].index >= 0 &&
  78                         (!g->node[j].on_stack ||
  79                          g->node[j].index > g->node[i].min_index))
  80                         continue;
  81
  82                 f = follows(i, j, user);
  83                 if (f < 0)
  84                         return -1;
  85                 if (!f)
  86                         continue;
  87
  88                 if (g->node[j].index < 0) {
  89                         isl_tarjan_components(g, j, follows, user);
  90                         if (g->node[j].min_index < g->node[i].min_index)
  91                                 g->node[i].min_index = g->node[j].min_index;
  92                 } else if (g->node[j].index < g->node[i].min_index)
  93                         g->node[i].min_index = g->node[j].index;
  94         }
  95
  96         if (g->node[i].index != g->node[i].min_index)
  97                 return 0;
  98
  99         do {
 100                 j = g->stack[--g->sp];
 101                 g->node[j].on_stack = 0;
 102                 g->order[g->op++] = j;
 103         } while (j != i);
 104         g->order[g->op++] = -1;
 105
 106         return 0;
 107 }
 108
 109 /* Decompose the graph with "len" nodes and edges defined by "follows"
 110  * into strongly connected components (SCCs).
 111  * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
 112  * It should return -1 on error.
 113  *
 114  * If SCC a contains a node i that follows a node j in another SCC b
 115  * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b
 116  * in the result.
 117  */
 118 struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
 119         int (*follows)(int i, int j, void *user), void *user)
 120 {
 121         int i;
 122         struct isl_tarjan_graph *g = NULL;
 123
 124         g = isl_tarjan_graph_alloc(ctx, len);
 125         if (!g)
 126                 return NULL;
 127         for (i = len - 1; i >= 0; --i) {
 128                 if (g->node[i].index >= 0)
 129                         continue;
 130                 if (isl_tarjan_components(g, i, follows, user) < 0)
 131                         goto error;
 132         }
 133
 134         return g;
 135 error:
 136         isl_tarjan_graph_free(g);
 137         return NULL;
 138 }