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 */ 10 struct 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 */ 26 struct 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 36 struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len, 37 isl_bool (*follows)(int i, int j, void *user), void *user); 38 struct isl_tarjan_graph *isl_tarjan_graph_component(isl_ctx *ctx, int len, 39 int node, isl_bool (*follows)(int i, int j, void *user), void *user); 40 struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g); 41 42 #endif 43