1/* 2 * Copyright 2010-2011 INRIA Saclay 3 * Copyright 2012 Ecole Normale Superieure 4 * 5 * Use of this software is governed by the MIT license 6 * 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, France 10 * and Ecole Normale Superieure, 45 rue d���Ulm, 75230 Paris, France 11 */ 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 components 60 * 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 b 116 * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b 117 * 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 component 145 * 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