| 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 | |
|---|
