Line data Source code
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 0 : struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g)
18 : {
19 0 : if (!g)
20 0 : return NULL;
21 0 : free(g->node);
22 0 : free(g->stack);
23 0 : free(g->order);
24 0 : free(g);
25 0 : return NULL;
26 : }
27 :
28 0 : 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 0 : g = isl_calloc_type(ctx, struct isl_tarjan_graph);
34 0 : if (!g)
35 0 : return NULL;
36 0 : g->len = len;
37 0 : g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);
38 0 : if (len && !g->node)
39 0 : goto error;
40 0 : for (i = 0; i < len; ++i)
41 0 : g->node[i].index = -1;
42 0 : g->stack = isl_alloc_array(ctx, int, len);
43 0 : if (len && !g->stack)
44 0 : goto error;
45 0 : g->order = isl_alloc_array(ctx, int, 2 * len);
46 0 : if (len && !g->order)
47 0 : goto error;
48 :
49 0 : g->sp = 0;
50 0 : g->index = 0;
51 0 : g->op = 0;
52 :
53 0 : return g;
54 : error:
55 0 : isl_tarjan_graph_free(g);
56 0 : 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 0 : 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 0 : g->node[i].index = g->index;
68 0 : g->node[i].min_index = g->index;
69 0 : g->node[i].on_stack = 1;
70 0 : g->index++;
71 0 : g->stack[g->sp++] = i;
72 :
73 0 : for (j = g->len - 1; j >= 0; --j) {
74 : isl_bool f;
75 :
76 0 : if (j == i)
77 0 : continue;
78 0 : if (g->node[j].index >= 0 &&
79 0 : (!g->node[j].on_stack ||
80 0 : g->node[j].index > g->node[i].min_index))
81 0 : continue;
82 :
83 0 : f = follows(i, j, user);
84 0 : if (f < 0)
85 0 : return isl_stat_error;
86 0 : if (!f)
87 0 : continue;
88 :
89 0 : if (g->node[j].index < 0) {
90 0 : isl_tarjan_components(g, j, follows, user);
91 0 : if (g->node[j].min_index < g->node[i].min_index)
92 0 : g->node[i].min_index = g->node[j].min_index;
93 0 : } else if (g->node[j].index < g->node[i].min_index)
94 0 : g->node[i].min_index = g->node[j].index;
95 : }
96 :
97 0 : if (g->node[i].index != g->node[i].min_index)
98 0 : return isl_stat_ok;
99 :
100 : do {
101 0 : j = g->stack[--g->sp];
102 0 : g->node[j].on_stack = 0;
103 0 : g->order[g->op++] = j;
104 0 : } while (j != i);
105 0 : g->order[g->op++] = -1;
106 :
107 0 : 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 0 : 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 0 : struct isl_tarjan_graph *g = NULL;
124 :
125 0 : g = isl_tarjan_graph_alloc(ctx, len);
126 0 : if (!g)
127 0 : return NULL;
128 0 : for (i = len - 1; i >= 0; --i) {
129 0 : if (g->node[i].index >= 0)
130 0 : continue;
131 0 : if (isl_tarjan_components(g, i, follows, user) < 0)
132 0 : return isl_tarjan_graph_free(g);
133 : }
134 :
135 0 : 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 0 : 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 0 : g = isl_tarjan_graph_alloc(ctx, len);
153 0 : if (!g)
154 0 : return NULL;
155 0 : if (isl_tarjan_components(g, node, follows, user) < 0)
156 0 : return isl_tarjan_graph_free(g);
157 :
158 0 : return g;
159 : }
|
