DAG的2D布局算法是否允许固定一个轴上的位置？

Question

我有一个大约3.300个顶点的DAG,它可以通过dot一个或多或少的简单树很成功地布局(事情变得复杂,因为顶点可以有不同的前导来自不同的排名,所以交叉频繁).在图中每个顶点应运而生在原始处理的特定时间,我想在布局一个轴表示时间:边缘关系像a -> v, b -> v装置,其a和b应运而生在之前一些特定时间v.

是否有DAG的布局算法允许我在一个轴上指定位置(或至少是距离),并在另一个轴上提出关于边缘交叉的最佳布局？

Answer 1

您可以对DAG进行拓扑排序,以使顶点按照每个边缘的方式排序,顶点先于.x->yxy

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

使用它你可以很容易地表示DAG如下:

Answer 2

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

此StackOverflow链接可能会帮助您：绘制有向无环图：最小化边缘交叉？

我想您的问题与图形布局的美观方式有关。一些启发式的文章中描述的算法，绘制图形概述，力指向绘图算法。可能有关平面图或几乎平面图的信息也可以为您提供帮助。

Wiki页面“ 平面图，交叉数（图论）”中介绍了一些检查和绘制平面图的算法。StackOverflow问题中介绍了用于平面图形绘制的库和算法。如何检查图形是否为平面图形？例如，GA文章中最大平面图的直线网格绘图的作者将遗传算法用于直线网格绘图。

几乎平面图，良好的描述中的文章给出了一个平面图形加边缘的直线深冲性能，几乎平面图的交叉数。

尝试根据您的条件以一轴对齐的方式修改原始算法。