graphviz - 仅使用 graphviz 工具生成传递闭包

Question

我需要处理点格式的有向图并获得子图(实际上是一个节点)的传递闭包。

例如，给定

 A -> B;
 E -> B;
 B -> C;
 C -> D;

我想得到节点A形成的子图的传递闭包:

 A -> B;
 B -> C;
 C -> D;

我知道这在 python 和许多其他语言中是可能的，但我试图仅使用命令行 graphviz 工具来实现这一点。

有什么简单的方法吗？ (我做了 rtfm 的 dot、tred、patchwork...但没有任何运气)。

Answer 1

gvpr应该能够执行这个任务。现在我要尝试一下...

编辑并不容易，但这可能是一个起点

-- 文件closure.gprv

BEGIN {
 int to_visit[];
 void add_req(node_t N) {
  edge_t e;
  for (e = fstout(N); e; e = nxtout(e))
   to_visit[e.head.name] = 1;
 }
}

BEG_G {
 $tvtype = TV_fwd;
 $tvroot = node($, "A");
 to_visit[$tvroot.name] = 1;
 add_req($tvroot);
 graph_t g = graph("A closure", "D");
}

N {
 if (to_visit[$.name]) {
  copy(g, $);
  add_req($);
 }
}

END_G {
 $O = g;
}

-- 文件closure.gv

digraph closure {
 A -> B;
 E -> B;
 B -> C;
 C -> D;
}

--命令和结果

gvpr -f closure.gprv closure.gv
digraph "A closure" {
    A;
    B;
    C;
    D;
}

编辑这个其他版本更完整，因为它也构建了边缘

BEGIN {
 int to_visit[];
 void add_req(node_t N) {
  edge_t e;
  for (e = fstout(N); e; e = nxtout(e))
   to_visit[e.head.name] = 1;
 }
}

BEG_G {
 $tvtype = TV_fwd;
 $tvroot = node($, "A");
 to_visit[$tvroot.name] = 1;
 add_req($tvroot);
 graph_t g = graph("A closure", "D");
}

E {
 if (to_visit[$.tail.name]) {
  copy(g, $);
  add_req($.head);
 }
}

END_G {
 $O = g;
}

产量

gvpr -f closure.gprv closure.gv
digraph "A closure" {
    A -> B;
    B -> C;
    C -> D;
}