160 lines · c
1/*2 * Copyright 2010-2011 INRIA Saclay3 * Copyright 2012 Ecole Normale Superieure4 *5 * Use of this software is governed by the MIT license6 *7 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,8 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,9 * 91893 Orsay, France10 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France11 */12 13#include <stdlib.h>14#include <isl/ctx.h>15#include <isl_tarjan.h>16 17struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g)18{19 if (!g)20 return NULL;21 free(g->node);22 free(g->stack);23 free(g->order);24 free(g);25 return NULL;26}27 28static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)29{30 struct isl_tarjan_graph *g;31 int i;32 33 g = isl_calloc_type(ctx, struct isl_tarjan_graph);34 if (!g)35 return NULL;36 g->len = len;37 g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);38 if (len && !g->node)39 goto error;40 for (i = 0; i < len; ++i)41 g->node[i].index = -1;42 g->stack = isl_alloc_array(ctx, int, len);43 if (len && !g->stack)44 goto error;45 g->order = isl_alloc_array(ctx, int, 2 * len);46 if (len && !g->order)47 goto error;48 49 g->sp = 0;50 g->index = 0;51 g->op = 0;52 53 return g;54error:55 isl_tarjan_graph_free(g);56 return NULL;57}58 59/* Perform Tarjan's algorithm for computing the strongly connected components60 * in the graph with g->len nodes and with edges defined by "follows".61 */62static isl_stat isl_tarjan_components(struct isl_tarjan_graph *g, int i,63 isl_bool (*follows)(int i, int j, void *user), void *user)64{65 int j;66 67 g->node[i].index = g->index;68 g->node[i].min_index = g->index;69 g->node[i].on_stack = 1;70 g->index++;71 g->stack[g->sp++] = i;72 73 for (j = g->len - 1; j >= 0; --j) {74 isl_bool f;75 76 if (j == i)77 continue;78 if (g->node[j].index >= 0 &&79 (!g->node[j].on_stack ||80 g->node[j].index > g->node[i].min_index))81 continue;82 83 f = follows(i, j, user);84 if (f < 0)85 return isl_stat_error;86 if (!f)87 continue;88 89 if (g->node[j].index < 0) {90 isl_tarjan_components(g, j, follows, user);91 if (g->node[j].min_index < g->node[i].min_index)92 g->node[i].min_index = g->node[j].min_index;93 } else if (g->node[j].index < g->node[i].min_index)94 g->node[i].min_index = g->node[j].index;95 }96 97 if (g->node[i].index != g->node[i].min_index)98 return isl_stat_ok;99 100 do {101 j = g->stack[--g->sp];102 g->node[j].on_stack = 0;103 g->order[g->op++] = j;104 } while (j != i);105 g->order[g->op++] = -1;106 107 return isl_stat_ok;108}109 110/* Decompose the graph with "len" nodes and edges defined by "follows"111 * into strongly connected components (SCCs).112 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.113 * It should return -1 on error.114 *115 * If SCC a contains a node i that follows a node j in another SCC b116 * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b117 * in the result.118 */119struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,120 isl_bool (*follows)(int i, int j, void *user), void *user)121{122 int i;123 struct isl_tarjan_graph *g = NULL;124 125 g = isl_tarjan_graph_alloc(ctx, len);126 if (!g)127 return NULL;128 for (i = len - 1; i >= 0; --i) {129 if (g->node[i].index >= 0)130 continue;131 if (isl_tarjan_components(g, i, follows, user) < 0)132 return isl_tarjan_graph_free(g);133 }134 135 return g;136}137 138/* Decompose the graph with "len" nodes and edges defined by "follows"139 * into the strongly connected component (SCC) that contains "node"140 * as well as all SCCs that are followed by this SCC.141 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.142 * It should return -1 on error.143 *144 * The SCC containing "node" will appear as the last component145 * in g->order.146 */147struct isl_tarjan_graph *isl_tarjan_graph_component(isl_ctx *ctx, int len,148 int node, isl_bool (*follows)(int i, int j, void *user), void *user)149{150 struct isl_tarjan_graph *g;151 152 g = isl_tarjan_graph_alloc(ctx, len);153 if (!g)154 return NULL;155 if (isl_tarjan_components(g, node, follows, user) < 0)156 return isl_tarjan_graph_free(g);157 158 return g;159}160