152a25237STobias Grosser #ifndef ISL_TARJAN_H 252a25237STobias Grosser #define ISL_TARJAN_H 352a25237STobias Grosser 452a25237STobias Grosser /* Structure for representing the nodes in the graph being traversed 552a25237STobias Grosser * using Tarjan's algorithm. 652a25237STobias Grosser * index represents the order in which nodes are visited. 752a25237STobias Grosser * min_index is the index of the root of a (sub)component. 852a25237STobias Grosser * on_stack indicates whether the node is currently on the stack. 952a25237STobias Grosser */ 1052a25237STobias Grosser struct isl_tarjan_node { 1152a25237STobias Grosser int index; 1252a25237STobias Grosser int min_index; 1352a25237STobias Grosser int on_stack; 1452a25237STobias Grosser }; 1552a25237STobias Grosser 1652a25237STobias Grosser /* Structure for representing the graph being traversed 1752a25237STobias Grosser * using Tarjan's algorithm. 1852a25237STobias Grosser * len is the number of nodes 1952a25237STobias Grosser * node is an array of nodes 2052a25237STobias Grosser * stack contains the nodes on the path from the root to the current node 2152a25237STobias Grosser * sp is the stack pointer 2252a25237STobias Grosser * index is the index of the last node visited 2352a25237STobias Grosser * order contains the elements of the components separated by -1 2452a25237STobias Grosser * op represents the current position in order 2552a25237STobias Grosser */ 2652a25237STobias Grosser struct isl_tarjan_graph { 2752a25237STobias Grosser int len; 2852a25237STobias Grosser struct isl_tarjan_node *node; 2952a25237STobias Grosser int *stack; 3052a25237STobias Grosser int sp; 3152a25237STobias Grosser int index; 3252a25237STobias Grosser int *order; 3352a25237STobias Grosser int op; 3452a25237STobias Grosser }; 3552a25237STobias Grosser 3652a25237STobias Grosser struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len, 37b2f39926STobias Grosser isl_bool (*follows)(int i, int j, void *user), void *user); 38*a7f1e040STobias Grosser struct isl_tarjan_graph *isl_tarjan_graph_component(isl_ctx *ctx, int len, 39*a7f1e040STobias Grosser int node, isl_bool (*follows)(int i, int j, void *user), void *user); 40*a7f1e040STobias Grosser struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g); 4152a25237STobias Grosser 4252a25237STobias Grosser #endif 43