是否有一个选项可以自动删除点图中的“冗余”边？

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

那么，有这样的选择吗？

Answer 1

根据@marapet的回答，我创建了一个脚本，我想也许其他人会从拥有一个副本中受益。它也在 Snap 中！ C++ 作为 clean-dependency.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 数据并修复它要困难得多。但是，就我而言，我可以访问您可能没有的数据。

Answer 2

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

最简单的方法通常是只在 graphviz 脚本中包含首先需要的边。如果这是不可能的，您可以使用

gvpr

（graphviz 模式扫描和处理语言）处理您的图形，然后将其输出输出到布局的点。

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

Answer 3

还有与 graphviz 一起分发的

tred

程序。

tred 计算有向图的传递约简，并将结果图打印到标准输出。这消除了传递性隐含的边缘。节点和子图不会受到其他影响。简化图的“含义”和有效性取决于应用程序。 tred 作为 dot 预处理器特别有用，可以减少密集布局中的混乱。