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
);