流氓图的支配树

Question

有没有一种方法可以使用更命令的方法从 Graph type 计算支配树？语言是否支持直接创建这样的数据结构？

我正在尝试使用以下算法 (here is the link for the original article) 从图中提取支配树：

但是我在调整那些 for 和 while 语句时遇到了问题。

Answer 1

有一些选择要做，例如如何表示输出支配树。一种典型的方法是再次选择图形。如果您愿意，稍后可以通过另一个函数将图形转换为构造函数树。

鉴于 Graph[&T] 的选择，以下模板可以成为给定算法到 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;
}{

然而，没有必要通过先反转它然后不断查找前辈来进入图的“pred”形式，我们也可以直接在边上循环，这要快得多：

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;
}

直接来自龙书中定义的基本定点求解器（以及您引用的论文中的方程式 3.2）。（请注意，我只是输入了这个，还没有测试过，所以它可能有问题）：

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;
}

（与 Set 模块中的库函数相交）

这是一个“关系演算”解决方案，它使用 reachX 库函数和 returns 从每个节点到它支配的节点集的关系来解决问题（取自 Rascal文档文件):

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};
}

流氓图的支配树

Dominator Tree of a Rascal Graph

functional-programming

graph

rascal