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 17void isl_tarjan_graph_free(struct isl_tarjan_graph *g) 18{ 19 if (!g) 20 return; 21 free(g->node); 22 free(g->stack); 23 free(g->order); 24 free(g); 25} 26 27static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len) 28{ 29 struct isl_tarjan_graph *g; 30 int i; 31 32 g = isl_calloc_type(ctx, struct isl_tarjan_graph); 33 if (!g) 34 return NULL; 35 g->len = len; 36 g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len); 37 if (len && !g->node) 38 goto error; 39 for (i = 0; i < len; ++i) 40 g->node[i].index = -1; 41 g->stack = isl_alloc_array(ctx, int, len); 42 if (len && !g->stack) 43 goto error; 44 g->order = isl_alloc_array(ctx, int, 2 * len); 45 if (len && !g->order) 46 goto error; 47 48 g->sp = 0; 49 g->index = 0; 50 g->op = 0; 51 52 return g; 53error: 54 isl_tarjan_graph_free(g); 55 return NULL; 56} 57 58/* Perform Tarjan's algorithm for computing the strongly connected components 59 * in the graph with g->len nodes and with edges defined by "follows". 60 */ 61static int isl_tarjan_components(struct isl_tarjan_graph *g, int i, 62 int (*follows)(int i, int j, void *user), void *user) 63{ 64 int j; 65 66 g->node[i].index = g->index; 67 g->node[i].min_index = g->index; 68 g->node[i].on_stack = 1; 69 g->index++; 70 g->stack[g->sp++] = i; 71 72 for (j = g->len - 1; j >= 0; --j) { 73 int f; 74 75 if (j == i) 76 continue; 77 if (g->node[j].index >= 0 && 78 (!g->node[j].on_stack || 79 g->node[j].index > g->node[i].min_index)) 80 continue; 81 82 f = follows(i, j, user); 83 if (f < 0) 84 return -1; 85 if (!f) 86 continue; 87 88 if (g->node[j].index < 0) { 89 isl_tarjan_components(g, j, follows, user); 90 if (g->node[j].min_index < g->node[i].min_index) 91 g->node[i].min_index = g->node[j].min_index; 92 } else if (g->node[j].index < g->node[i].min_index) 93 g->node[i].min_index = g->node[j].index; 94 } 95 96 if (g->node[i].index != g->node[i].min_index) 97 return 0; 98 99 do { 100 j = g->stack[--g->sp]; 101 g->node[j].on_stack = 0; 102 g->order[g->op++] = j; 103 } while (j != i); 104 g->order[g->op++] = -1; 105 106 return 0; 107} 108 109/* Decompose the graph with "len" nodes and edges defined by "follows" 110 * into strongly connected components (SCCs). 111 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise. 112 * It should return -1 on error. 113 * 114 * If SCC a contains a node i that follows a node j in another SCC b 115 * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b 116 * in the result. 117 */ 118struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len, 119 int (*follows)(int i, int j, void *user), void *user) 120{ 121 int i; 122 struct isl_tarjan_graph *g = NULL; 123 124 g = isl_tarjan_graph_alloc(ctx, len); 125 if (!g) 126 return NULL; 127 for (i = len - 1; i >= 0; --i) { 128 if (g->node[i].index >= 0) 129 continue; 130 if (isl_tarjan_components(g, i, follows, user) < 0) 131 goto error; 132 } 133 134 return g; 135error: 136 isl_tarjan_graph_free(g); 137 return NULL; 138} 139