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
17void isl_tarjan_graph_free(struct isl_tarjan_graph *g)
18{
19	if (!g)
20		return;
21	free(g->node);
22	free(g->stack);
23	free(g->order);
24	free(g);
25}
26
27static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)
28{
29	struct isl_tarjan_graph *g;
30	int i;
31
32	g = isl_calloc_type(ctx, struct isl_tarjan_graph);
33	if (!g)
34		return NULL;
35	g->len = len;
36	g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);
37	if (len && !g->node)
38		goto error;
39	for (i = 0; i < len; ++i)
40		g->node[i].index = -1;
41	g->stack = isl_alloc_array(ctx, int, len);
42	if (len && !g->stack)
43		goto error;
44	g->order = isl_alloc_array(ctx, int, 2 * len);
45	if (len && !g->order)
46		goto error;
47
48	g->sp = 0;
49	g->index = 0;
50	g->op = 0;
51
52	return g;
53error:
54	isl_tarjan_graph_free(g);
55	return NULL;
56}
57
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".
60 */
61static int isl_tarjan_components(struct isl_tarjan_graph *g, int i,
62	int (*follows)(int i, int j, void *user), void *user)
63{
64	int j;
65
66	g->node[i].index = g->index;
67	g->node[i].min_index = g->index;
68	g->node[i].on_stack = 1;
69	g->index++;
70	g->stack[g->sp++] = i;
71
72	for (j = g->len - 1; j >= 0; --j) {
73		int f;
74
75		if (j == i)
76			continue;
77		if (g->node[j].index >= 0 &&
78			(!g->node[j].on_stack ||
79			 g->node[j].index > g->node[i].min_index))
80			continue;
81
82		f = follows(i, j, user);
83		if (f < 0)
84			return -1;
85		if (!f)
86			continue;
87
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;
94	}
95
96	if (g->node[i].index != g->node[i].min_index)
97		return 0;
98
99	do {
100		j = g->stack[--g->sp];
101		g->node[j].on_stack = 0;
102		g->order[g->op++] = j;
103	} while (j != i);
104	g->order[g->op++] = -1;
105
106	return 0;
107}
108
109/* Decompose the graph with "len" nodes and edges defined by "follows"
110 * into strongly connected components (SCCs).
111 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
112 * It should return -1 on error.
113 *
114 * If SCC a contains a node i that follows a node j in another SCC b
115 * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b
116 * in the result.
117 */
118struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
119	int (*follows)(int i, int j, void *user), void *user)
120{
121	int i;
122	struct isl_tarjan_graph *g = NULL;
123
124	g = isl_tarjan_graph_alloc(ctx, len);
125	if (!g)
126		return NULL;
127	for (i = len - 1; i >= 0; --i) {
128		if (g->node[i].index >= 0)
129			continue;
130		if (isl_tarjan_components(g, i, follows, user) < 0)
131			goto error;
132	}
133
134	return g;
135error:
136	isl_tarjan_graph_free(g);
137	return NULL;
138}
139