1#ifndef ISL_TARJAN_H
2#define ISL_TARJAN_H
3
4/* Structure for representing the nodes in the graph being traversed
5 * using Tarjan's algorithm.
6 * index represents the order in which nodes are visited.
7 * min_index is the index of the root of a (sub)component.
8 * on_stack indicates whether the node is currently on the stack.
9 */
10struct isl_tarjan_node {
11	int index;
12	int min_index;
13	int on_stack;
14};
15
16/* Structure for representing the graph being traversed
17 * using Tarjan's algorithm.
18 * len is the number of nodes
19 * node is an array of nodes
20 * stack contains the nodes on the path from the root to the current node
21 * sp is the stack pointer
22 * index is the index of the last node visited
23 * order contains the elements of the components separated by -1
24 * op represents the current position in order
25 */
26struct isl_tarjan_graph {
27	int len;
28	struct isl_tarjan_node *node;
29	int *stack;
30	int sp;
31	int index;
32	int *order;
33	int op;
34};
35
36struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
37	int (*follows)(int i, int j, void *user), void *user);
38void isl_tarjan_graph_free(struct isl_tarjan_graph *g);
39
40#endif
41