Home | History | Annotate | Line # | Download | only in dist 
      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 dUlm, 75230 Paris, France
     11  */
     12 
     13 #include <stdlib.h>
     14 #include <isl/ctx.h>
     15 #include <isl_tarjan.h>
     16 
     17 struct 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 
     28 static 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;
     54 error:
     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  */
     62 static 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  */
    119 struct 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  */
    147 struct 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