是否有一种针对DAG的二维布局算法，可以使其中一个轴上的位置固定？

Question

我有一个包含约3300个顶点的DAG，可以通过"dot"算法布局成一个相对简单的树形结构（由于顶点可能来自不同级别的多个前驱者，因此交叉频繁发生，事情变得更加复杂）。图中的每个顶点都在原始进程的特定时间产生，并且我想要布局中的一个轴表示时间：像"a -> v, b -> v"这样的边关系意味着"a"和"b"在一些特定时间之前就存在，而"v"则是在它们之后产生的。

是否有一种DAG布局算法可以让我指定一个轴上的位置（或至少距离），并在另一个轴上优化边交叉问题？

- user2722968

Answer 1

你可以对DAG进行拓扑排序，使得每个边x->y中的顶点x在y之前。因此，如果有a -> v, b -> v，则会得到类似于a，b，v或b，a，v的结果。使用这种方法，你可以轻松地表示像这样的DAG：

- Arturo Menchaca

---

Hrms，我应该自己想到那个...虽然这种方法非常简单且易于实现：但是否有实际证据表明对于任何DAG，结果在边交叉方面是最优的？ - user2722968

我已经找到了如何在networkx中进行拓扑排序，但是真的不知道如何按照你的答案中的那样以拓扑排序顺序绘制。你能给我一些提示吗？ - kawing-chiu

Answer 2

是的，正如@Arturo-Menchaca所说，拓扑排序可能有助于减少边重叠计数。但这可能不是最优解。边交叉最小化问题没有好的算法。交叉最小化问题是NP完全问题。启发式算法被应用于解决此问题。

这个StackOverflow链接可能会对您有所帮助：Drawing Directed Acyclic Graphs: Minimizing edge crossing? 我认为你的问题与图形布局的美学方式有关。一些启发式算法在文章Overview of algorithms for graph drawing，Force-Directed Drawing Algorithms中有描述。有关平面图或几乎平面图的信息也可能对您有所帮助。

一些用于检查和绘制平面图的算法的评论在维基页面Planar graph，Crossing number (graph theory)中有描述。平面图绘制的库和算法在StackOverflow问题How to check if a Graph is a Planar Graph or not?中有描述。例如，文章GA for straight-line grid drawings of maximal planar graphs的作者使用遗传算法进行直线网格绘制。

关于几乎平面图的良好描述在文章Straight-Line Drawability of a Planar Graph Plus an Edge，On the Crossing Number of Almost Planar Graphs中给出。

尝试使用单轴对齐条件修改原始算法。

- Didgeridoo

Answer 3

如果我理解正确，您希望最小化图形布局中边的交叉数量。如果是这样，那么答案是“不行”，因为在一般情况下已经证明了这个问题是NP完全问题。请参见这里，"Crossing Number is NP-Complete, Garey, Johnson"。

如果您只需要一个不是最优但足够好的解决方案，则有多篇文章涉及此主题，因为它与电路布局密切相关。大概通过搜索“crossing number heuristics”并查看一些论文摘要可能比我盲目猜测您的需求更好地解决您的任务。

- Ivan Smirnov