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
17struct 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
28static 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;
54error:
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 */
62static 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 */
119struct 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 */
147struct 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