有没有自动删除dot图中“冗余”边的选项？

Question

我为我的Debian项目创建了一个依赖关系的点图（见图片）。这些依赖包括冗余边。我希望有一个更简单的图形，不包含这些冗余边。我可以自己计算，但由于我在CMakeLists.txt和.cmake扩展中生成.dot文件，所以并不容易。

因此，我想知道dot或Graphviz是否有选项可以删除不需要的边。例如，顶部的snapwebsites项目依赖于csspp和advgetopt。由于cspp软件包已经依赖于advgetopt，所以snapwebsites和advgetopt之间的边是不必要的。

在有向图中，这意味着：

"snapwebsites" -> "advgetopt";     <-- "auto-remove" this one
"snapwebsites" -> "csspp";

"csspp" -> "advgetopt";

那么，有这样的选项吗？

最初的回答：无法确定。请提供更多上下文信息。

- Alexis Wilke

---

投票支持，因为我没有看到任何评论解释为什么这个问题被投票否决。至少我也是带着同样的问题来到这里的。 - Michael K

Answer 1

根据@marapet的回答，我编写了一个脚本，并认为其他人也可以受益于拥有副本。 它还在Snap！C ++中作为clean-dependencies.gvpr 。

# Run with:
#
#    /usr/bin/gvpr -o clean-dependencies.dot -f clean-dependencies.gvpr dependencies.dot
#
# Clean up the dependencies.svg from double dependencies
# In other words if A depends on B and C, and B also depends on C, we
# can remove the link between A amd C, it's not necessary in our file.

BEG_G {
    edge_t direct_edges[int];
    node_t children[int];

    node_t n = fstnode($G);
    while(n != NULL) {

        // 1. extract the current node direct children
        //
        int direct_pos = 0;
        edge_t e = fstout_sg($G, n);
        while(e != NULL) {
            direct_edges[direct_pos] = e;
            children[direct_pos] = opp(e, n);
            direct_pos = direct_pos + 1;
            e = nxtout_sg($G, e);
        }

        // 2. find all of the grand children
        //    and see whether some are duplicates, if so delete the
        //    original (direct) edge
        //
        int child_pos = direct_pos;
        int c = 0;
        for(c = 0; c < child_pos; ++c) {
            e = fstout_sg($G, children[c]);
            while(e != NULL) {
                node_t o = opp(e, children[c]);
                int idx;
                for(idx = 0; idx < direct_pos; ++idx) {
                    if(children[idx] == o) {
                        if(direct_edges[idx] != NULL) {
                            delete($G, direct_edges[idx]);
                            direct_edges[idx] = NULL;
                        }
                        break;
                    }
                }
                e = nxtout_sg($G, e);
            }
        }

        n = nxtnode_sg($G, n);
    }
}

END_G {
    $O = $G;
}

我想提到几点：gvpr函数似乎不能接受数组作为输入。此外，我最初尝试使用递归方法，但局部变量会被进一步的调用破坏（即在递归调用返回时，变量的值是来自子调用的值...所以变量是一个函数的“本地”的，但仍然只有一个实例，没有堆栈！）

希望以后的版本能解决这些问题。

$ gvpr -V
gvpr version 2.38.0 (20140413.2041)

相比尝试在CMake中解决我的图形问题，这已经是一种更简单的方法。

---

更新

我最终编写了一个Python脚本来完成这项工作。可以很容易地从定义为Makefile的树中删除重复项。但是，读取.dot数据并进行修复要困难得多。然而，在我的情况下，我可以访问该数据，您可能没有这个权限。

- Alexis Wilke

Answer 2

据我所知，内置没有这样的选项（我可能错了...）。

通常最简单的方法是在 graphviz 脚本中仅包含所需的边。如果不可能，您可以使用 gvpr （graphviz 模式扫描和处理语言）处理图形，然后将其输出到 dot 进行布局。

当然，这意味着您需要使用 gvpr 实现检测和抑制不需要的边缘，并且可以在需要时重复使用该脚本。

- marapet

---

没错，你也可以使用一些编程语言的Graphviz库（例如Python的pygraphviz）来处理和修改图形。 - Dany

@Dany，这可能比gvpr更好。我遇到了各种问题（请参见我的答案），这些问题在pygraphviz中可能不存在。 - Alexis Wilke