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 struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g)
  18 {
  19         if (!g)
  20                 return NULL;
  21         free(g->node);
  22         free(g->stack);
  23         free(g->order);
  24         free(g);
  25         return NULL;
  26 }
  27
  28 static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)
  29 {
  30         struct isl_tarjan_graph *g;
  31         int i;
  32
  33         g = isl_calloc_type(ctx, struct isl_tarjan_graph);
  34         if (!g)
  35                 return NULL;
  36         g->len = len;
  37         g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);
  38         if (len && !g->node)
  39                 goto error;
  40         for (i = 0; i < len; ++i)
  41                 g->node[i].index = -1;
  42         g->stack = isl_alloc_array(ctx, int, len);
  43         if (len && !g->stack)
  44                 goto error;
  45         g->order = isl_alloc_array(ctx, int, 2 * len);
  46         if (len && !g->order)
  47                 goto error;
  48
  49         g->sp = 0;
  50         g->index = 0;
  51         g->op = 0;
  52
  53         return g;
  54 error:
  55         isl_tarjan_graph_free(g);
  56         return NULL;
  57 }
  58
  59 /* Perform Tarjan's algorithm for computing the strongly connected components
  60  * in the graph with g->len nodes and with edges defined by "follows".
  61  */
  62 static isl_stat isl_tarjan_components(struct isl_tarjan_graph *g, int i,
  63         isl_bool (*follows)(int i, int j, void *user), void *user)
  64 {
  65         int j;
  66
  67         g->node[i].index = g->index;
  68         g->node[i].min_index = g->index;
  69         g->node[i].on_stack = 1;
  70         g->index++;
  71         g->stack[g->sp++] = i;
  72
  73         for (j = g->len - 1; j >= 0; --j) {
  74                 isl_bool f;
  75
  76                 if (j == i)
  77                         continue;
  78                 if (g->node[j].index >= 0 &&
  79                         (!g->node[j].on_stack ||
  80                          g->node[j].index > g->node[i].min_index))
  81                         continue;
  82
  83                 f = follows(i, j, user);
  84                 if (f < 0)
  85                         return isl_stat_error;
  86                 if (!f)
  87                         continue;
  88
  89                 if (g->node[j].index < 0) {
  90                         isl_tarjan_components(g, j, follows, user);
  91                         if (g->node[j].min_index < g->node[i].min_index)
  92                                 g->node[i].min_index = g->node[j].min_index;
  93                 } else if (g->node[j].index < g->node[i].min_index)
  94                         g->node[i].min_index = g->node[j].index;
  95         }
  96
  97         if (g->node[i].index != g->node[i].min_index)
  98                 return isl_stat_ok;
  99
 100         do {
 101                 j = g->stack[--g->sp];
 102                 g->node[j].on_stack = 0;
 103                 g->order[g->op++] = j;
 104         } while (j != i);
 105         g->order[g->op++] = -1;
 106
 107         return isl_stat_ok;
 108 }
 109
 110 /* Decompose the graph with "len" nodes and edges defined by "follows"
 111  * into strongly connected components (SCCs).
 112  * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
 113  * It should return -1 on error.
 114  *
 115  * If SCC a contains a node i that follows a node j in another SCC b
 116  * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b
 117  * in the result.
 118  */
 119 struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
 120         isl_bool (*follows)(int i, int j, void *user), void *user)
 121 {
 122         int i;
 123         struct isl_tarjan_graph *g = NULL;
 124
 125         g = isl_tarjan_graph_alloc(ctx, len);
 126         if (!g)
 127                 return NULL;
 128         for (i = len - 1; i >= 0; --i) {
 129                 if (g->node[i].index >= 0)
 130                         continue;
 131                 if (isl_tarjan_components(g, i, follows, user) < 0)
 132                         return isl_tarjan_graph_free(g);
 133         }
 134
 135         return g;
 136 }
 137
 138 /* Decompose the graph with "len" nodes and edges defined by "follows"
 139  * into the strongly connected component (SCC) that contains "node"
 140  * as well as all SCCs that are followed by this SCC.
 141  * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
 142  * It should return -1 on error.
 143  *
 144  * The SCC containing "node" will appear as the last component
 145  * in g->order.
 146  */
 147 struct isl_tarjan_graph *isl_tarjan_graph_component(isl_ctx *ctx, int len,
 148         int node, isl_bool (*follows)(int i, int j, void *user), void *user)
 149 {
 150         struct isl_tarjan_graph *g;
 151
 152         g = isl_tarjan_graph_alloc(ctx, len);
 153         if (!g)
 154                 return NULL;
 155         if (isl_tarjan_components(g, node, follows, user) < 0)
 156                 return isl_tarjan_graph_free(g);
 157
 158         return g;
 159 }