如何重新分配图形元素以最大限度地提高可读性？

How to redistribute graph elements to maximize readability?

我有一个由节点组成的图。每个节点可以有多个父节点 and/or 个子节点。我想显示该图和节点之间的连接。

但我不知道如何重新分配节点以最大限度地提高可读性。目前我面临以下问题：

此外，我只能垂直移动节点，不能水平移动，因为列数有限。

为了让自己更轻松，我尝试将节点放置在类似网格的模式中。我已经设法按列对它们进行分组。但是后来我不知何故需要遍历列并将它们与其他列进行比较以重新排列内容。而且我不知道从哪里开始。

UPD：我可能错了，但我觉得我的图形对齐问题在某种程度上与最短路径的典型图形问题有关。除了在我的例子中有多个路径应该同时计算并且有些节点只能通过一次。

在下图中，您可以看到我通过在纸上乱涂乱画而做出的近乎理想的重新分配（从左到右的方向显示父子连接）。

您可以实施 force directed drawing. Or you could use a graph drawing library that already supports force directed drawing, such as D3's force directed layout.

是图形布局和绘图问题。您可以采用以下两种方法之一

  1. 使用已有的库：有许多图形布局库可用，例如 GraphViz、Gephi、D3js 等。您可以直接使用它们的 API，也可以find applications/tools 建立在它们之上。但是要获得最佳布局，您需要猜测布局系列。例如分层图形布局（适用于密集但分层的图形，如流程图）树布局（当图形实际上是树或森林时使用。树有很多变体），径向树布局（同样适用于树，但在极地系统中），力导向布局（当您不知道哪种视觉结构最能代表数据时，这是一个很好的起点）。所有这些布局都会有许多自定义参数，如节点间距、节点和边缘之间的间距、绘图的整体纵横比等。 GraphViz Gephi

  2. 自己实现布局算法 可以在此处找到针对不同系列的图形绘制算法的详细介绍 Graph Drawing Handbook

如果您不想深入了解细节，这里是快速入门点

  1. 对于图表，进行拓扑排序并按照拓扑顺序将节点放置在图层中。它可以为您提供一个很好的起点，并帮助您避免不必要的交叉。网格在这里可能是个好主意。但是将节点按拓扑顺序放置在网格中。
  2. 或者，找到图形的生成树，使用树布局绘制生成树，然后添加剩余的边
  3. 对于树：使用递归的自下而上方法放置子树。对于径向树，做直线布局，然后转换到极坐标系
  4. 对于未知的家庭：使用力导向法。定义两个节点之间的力（例如 spring 力），然后通过迭代找到平衡点。

图形的最佳自动可视化是一个非常有趣的领域，人们正在这里尝试许多 ML 技术。