isl_tarjan.h

   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