43 lines · c
1#ifndef ISL_TARJAN_H2#define ISL_TARJAN_H3 4/* Structure for representing the nodes in the graph being traversed5 * 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 traversed17 * using Tarjan's algorithm.18 * len is the number of nodes19 * node is an array of nodes20 * stack contains the nodes on the path from the root to the current node21 * sp is the stack pointer22 * index is the index of the last node visited23 * order contains the elements of the components separated by -124 * op represents the current position in order25 */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 isl_bool (*follows)(int i, int j, void *user), void *user);38struct 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);40struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g);41 42#endif43