DAG是否有2D布局算法，可以修正一个轴上的位置？

我有一个约3.300个顶点的DAG，可以通过dot作为一个或多或少简单的树相当成功地布局（事情变得复杂，因为顶点可以有一个以上的前辈从一个完全不同的级别，所以交叉频繁）。图表中的每个顶点都是在原始过程中的特定时间生成的，我希望布局中的一个轴表示时间：a -> v, b -> v等边缘关系表示a和b在v之前的某个特定时间应运而生。DAG是否有2D布局算法，可以修正一个轴上的位置？

是否有DAG的布局算法，它允许我指定一个坐标轴上的位置（或至少是距离），并在另一个坐标轴上提供关于边缘交叉点的最佳布局？

来源

2016-09-22 user2722968

可以使DAG的topological sorting拥有的方式排序的顶点，每边x->y，顶点x来比y之前。

因此，如果你有a -> v, b -> v，你会得到类似a, b, v或b, a, v。

使用这一点，你可以轻松地表示DAG就像这样：

来源

2016-09-26 16:55:29

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

我已经找到了如何在'networkx'中进行拓扑排序，但实际上并不知道如何绘制拓扑排序顺序，就像在答案中一样。你能给我一些提示吗？ –

如果我的理解是否正确，那么你希望尽量减少你的图形布局边缘的交叉数。如果是这样，那么答案是“否”，因为这个问题在一般情况下被证明是NP完全的。见this，“交叉号码是NP-Complete，Garey，Johnson”。

如果您需要一个不是最优但足够好的解决方案，有多篇关于此主题的文章，因为它与电路布局密切相关。可能用谷歌搜索“穿越数字启发式”并查看一些文章的摘要将更好地解决您的任务，然后我试图盲目猜测您的需求。

来源

2016-09-30 18:18:37

是的，因为@ 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中给出。

尝试修改原始算法，使用您的条件与一个轴对齐。

来源

2016-09-30 20:52:09 Didgeridoo

DAG是否有2D布局算法，可以修正一个轴上的位置？

回答

相关问题