2 * Copyright 2010-2011 INRIA Saclay
3 * Copyright 2012 Ecole Normale Superieure
5 * Use of this software is governed by the GNU LGPLv2.1 license
7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
15 #include <isl_tarjan.h>
17 void isl_tarjan_graph_free(struct isl_tarjan_graph *g)
27 static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)
29 struct isl_tarjan_graph *g;
32 g = isl_calloc_type(ctx, struct isl_tarjan_graph);
36 g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);
39 for (i = 0; i < len; ++i)
40 g->node[i].index = -1;
41 g->stack = isl_alloc_array(ctx, int, len);
44 g->order = isl_alloc_array(ctx, int, 2 * len);
54 isl_tarjan_graph_free(g);
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".
61 static int isl_tarjan_components(struct isl_tarjan_graph *g, int i,
62 int (*follows)(int i, int j, void *user), void *user)
66 g->node[i].index = g->index;
67 g->node[i].min_index = g->index;
68 g->node[i].on_stack = 1;
70 g->stack[g->sp++] = i;
72 for (j = g->len - 1; j >= 0; --j) {
77 if (g->node[j].index >= 0 &&
78 (!g->node[j].on_stack ||
79 g->node[j].index > g->node[i].min_index))
82 f = follows(i, j, user);
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;
96 if (g->node[i].index != g->node[i].min_index)
100 j = g->stack[--g->sp];
101 g->node[j].on_stack = 0;
102 g->order[g->op++] = j;
104 g->order[g->op++] = -1;
109 /* Decompose the graph with "len" nodes and edges defined by "follows"
110 * into strongly connected components.
112 struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
113 int (*follows)(int i, int j, void *user), void *user)
116 struct isl_tarjan_graph *g = NULL;
118 g = isl_tarjan_graph_alloc(ctx, len);
121 for (i = len - 1; i >= 0; --i) {
122 if (g->node[i].index >= 0)
124 if (isl_tarjan_components(g, i, follows, user) < 0)
130 isl_tarjan_graph_free(g);