isl_tarjan.c

Go to the documentation of this file.

/*
 * Copyright 2010-2011 INRIA Saclay
 * Copyright 2012      Ecole Normale Superieure
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
 * 91893 Orsay, France
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
 */
 
#include <stdlib.h>
#include <isl/ctx.h>
#include <isl_tarjan.h>
 
struct isl_tarjan_graph *isl_tarjan_graph_free(struct isl_tarjan_graph *g)
{
  if (!g)
    return NULL;
  free(g->node);
  free(g->stack);
  free(g->order);
  free(g);
  return NULL;
}
 
static struct isl_tarjan_graph *isl_tarjan_graph_alloc(isl_ctx *ctx, int len)
{
  struct isl_tarjan_graph *g;
  int i;
 
  g = isl_calloc_type(ctx, struct isl_tarjan_graph);
  if (!g)
    return NULL;
  g->len = len;
  g->node = isl_alloc_array(ctx, struct isl_tarjan_node, len);
  if (len && !g->node)
    goto error;
  for (i = 0; i < len; ++i)
    g->node[i].index = -1;
  g->stack = isl_alloc_array(ctx, int, len);
  if (len && !g->stack)
    goto error;
  g->order = isl_alloc_array(ctx, int, 2 * len);
  if (len && !g->order)
    goto error;
 
  g->sp = 0;
  g->index = 0;
  g->op = 0;
 
  return g;
error:
  isl_tarjan_graph_free(g);
  return NULL;
}
 
/* Perform Tarjan's algorithm for computing the strongly connected components
 * in the graph with g->len nodes and with edges defined by "follows".
 */
static isl_stat isl_tarjan_components(struct isl_tarjan_graph *g, int i,
  isl_bool (*follows)(int i, int j, void *user), void *user)
{
  int j;
 
  g->node[i].index = g->index;
  g->node[i].min_index = g->index;
  g->node[i].on_stack = 1;
  g->index++;
  g->stack[g->sp++] = i;
 
  for (j = g->len - 1; j >= 0; --j) {
    isl_bool f;
 
    if (j == i)
      continue;
    if (g->node[j].index >= 0 &&
      (!g->node[j].on_stack ||
       g->node[j].index > g->node[i].min_index))
      continue;
 
    f = follows(i, j, user);
    if (f < 0)
      return isl_stat_error;
    if (!f)
      continue;
 
    if (g->node[j].index < 0) {
      isl_tarjan_components(g, j, follows, user);
      if (g->node[j].min_index < g->node[i].min_index)
        g->node[i].min_index = g->node[j].min_index;
    } else if (g->node[j].index < g->node[i].min_index)
      g->node[i].min_index = g->node[j].index;
  }
 
  if (g->node[i].index != g->node[i].min_index)
    return isl_stat_ok;
 
  do {
    j = g->stack[--g->sp];
    g->node[j].on_stack = 0;
    g->order[g->op++] = j;
  } while (j != i);
  g->order[g->op++] = -1;
 
  return isl_stat_ok;
}
 
/* Decompose the graph with "len" nodes and edges defined by "follows"
 * into strongly connected components (SCCs).
 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
 * It should return -1 on error.
 *
 * If SCC a contains a node i that follows a node j in another SCC b
 * (i.e., follows(i, j, user) returns 1), then SCC a will appear after SCC b
 * in the result.
 */
struct isl_tarjan_graph *isl_tarjan_graph_init(isl_ctx *ctx, int len,
  isl_bool (*follows)(int i, int j, void *user), void *user)
{
  int i;
  struct isl_tarjan_graph *g = NULL;
 
  g = isl_tarjan_graph_alloc(ctx, len);
  if (!g)
    return NULL;
  for (i = len - 1; i >= 0; --i) {
    if (g->node[i].index >= 0)
      continue;
    if (isl_tarjan_components(g, i, follows, user) < 0)
      return isl_tarjan_graph_free(g);
  }
 
  return g;
}
 
/* Decompose the graph with "len" nodes and edges defined by "follows"
 * into the strongly connected component (SCC) that contains "node"
 * as well as all SCCs that are followed by this SCC.
 * follows(i, j, user) should return 1 if "i" follows "j" and 0 otherwise.
 * It should return -1 on error.
 *
 * The SCC containing "node" will appear as the last component
 * in g->order.
 */
struct isl_tarjan_graph *isl_tarjan_graph_component(isl_ctx *ctx, int len,
  int node, isl_bool (*follows)(int i, int j, void *user), void *user)
{
  struct isl_tarjan_graph *g;
 
  g = isl_tarjan_graph_alloc(ctx, len);
  if (!g)
    return NULL;
  if (isl_tarjan_components(g, node, follows, user) < 0)
    return isl_tarjan_graph_free(g);
 
  return g;
}