Dominator Tree of a Rascal Graph

Question

Is there a way to calculate the dominator tree from the Graph type using a more imperative approach? The language has a support to create such data structure directly?

I'm trying to extract a dominator tree from a Graph using the following algorithm (here is the link for the original article):

But I'm having trouble in adapting those for and while statements.

Answer 1

There are some choices to make, like for example how to represent the output dominator tree. One typical way is to choose Graph again. Later you could transform the Graph to a constructor tree if you like by another function.

Given that choice for Graph[&T], the following template could become a rather literal translation of the given algorithm into Rascal:

Graph[&T] dominators(Graph[&T] graph, &T root) {
  result = {};
  V = carrier(graph);
  Pred = graph<to,from>;

  solve(result) {
     for (v <- V, u <- Pred[v]) {
        if (...)
     }
  }
  return result;
}{

However it is unnecessary to go to the "pred" form of a graph by first inverting it and then continously looking up predecessors, we can directly loop over the edges as well, and this is much much faster:

Graph[&T] dominators(Graph[&T] graph, &T root) {
  result = {};
  
  solve(result) {
     for (<u, v> <- graph) { // u is the predecessor of v
        if (...) {
          result += { };
        }
     }
  }

  return result;
}

A basic fixed point solver directly from the definition in the Dragon book (and also equation 3.2 in the thesis you cited). (Note I just typed this in, haven't tested it so it may be buggy):

rel[&T, set[&T]] dominators(graph[&T] graph) {
  nodes = carrier(graph);
  result = {};
  preds = graph<to,from>;

  solve(result) {
    for (n <- nodes) {
      result[n] = {n} + intersect({result[p] | p <- preds[n]?{}});
    }
  }

  return result;
}

(with intersect a library function from the Set module)

And here is a "relational calculus" solution, which solves the problem using the reachX library function and returns a relation from each node to the set of nodes it dominates (taken from Rascal documentation files):

rel[&T, set[&T]] dominators(rel[&T,&T] PRED, &T ROOT) {
  set[&T] VERTICES = carrier(PRED); 
  return { <V, (VERTICES - {V, ROOT}) - reachX({ROOT}, {V}, PRED)> | &T V : VERTICES};
}