-/* Perform Tarjan's algorithm for computing the strongly connected components
- * in the graph with the disjuncts of "map" as vertices and with an
- * edge between any pair of disjuncts such that the first has
- * to be applied after the second.
- */
-static int power_components_tarjan(struct basic_map_sort *s,
- __isl_keep isl_basic_map **list, int i)
-{
- int j;
-
- s->node[i].index = s->index;
- s->node[i].min_index = s->index;
- s->node[i].on_stack = 1;
- s->index++;
- s->stack[s->sp++] = i;
-
- for (j = s->len - 1; j >= 0; --j) {
- int f;
-
- if (j == i)
- continue;
- if (s->node[j].index >= 0 &&
- (!s->node[j].on_stack ||
- s->node[j].index > s->node[i].min_index))
- continue;
-
- f = basic_map_follows(list[i], list[j], &s->check_closed);
- if (f < 0)
- return -1;
- if (!f)
- continue;
-
- if (s->node[j].index < 0) {
- power_components_tarjan(s, list, j);
- if (s->node[j].min_index < s->node[i].min_index)
- s->node[i].min_index = s->node[j].min_index;
- } else if (s->node[j].index < s->node[i].min_index)
- s->node[i].min_index = s->node[j].index;
- }
-
- if (s->node[i].index != s->node[i].min_index)
- return 0;
-
- do {
- j = s->stack[--s->sp];
- s->node[j].on_stack = 0;
- s->order[s->op++] = j;
- } while (j != i);
- s->order[s->op++] = -1;
-
- return 0;
-}
-
-/* Decompose the "len" basic relations in "list" into strongly connected
- * components.
- */
-static struct basic_map_sort *basic_map_sort_init(isl_ctx *ctx, int len,
- __isl_keep isl_basic_map **list)
-{
- int i;
- struct basic_map_sort *s = NULL;
-
- s = basic_map_sort_alloc(ctx, len);
- if (!s)
- return NULL;
- for (i = len - 1; i >= 0; --i) {
- if (s->node[i].index >= 0)
- continue;
- if (power_components_tarjan(s, list, i) < 0)
- goto error;
- }
-
- return s;
-error:
- basic_map_sort_free(s);
- return NULL;
-}
-