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
isl_tarjan_graph_free(struct isl_tarjan_graph * g)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
isl_tarjan_graph_alloc(isl_ctx * ctx,int len)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 */
isl_tarjan_components(struct isl_tarjan_graph * g,int i,isl_bool (* follows)(int i,int j,void * user),void * user)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 */
isl_tarjan_graph_init(isl_ctx * ctx,int len,isl_bool (* follows)(int i,int j,void * user),void * user)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 */
isl_tarjan_graph_component(isl_ctx * ctx,int len,int node,isl_bool (* follows)(int i,int j,void * user),void * user)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 }
160