Home | History | Annotate | Line # | Download | only in dist 
      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