如何线性排列图形,没有重叠？

Question

我正在尝试为Blender编写一个插件,它可以自动排列节点树,没有重叠或连接流向左侧.我可以访问节点列表,它们的位置,尺寸以及连接/链接列表.该图从左到右运行,可以有多个开始和结束节点.节点的输出无法连接到节点之前的输入,或者它自己的输入(没有循环依赖性.)

有没有人知道一篇专注于编写可以改变这种情况的文章或文章:

进入这个？

我最初提出的方法是:对于没有输入连接的所有节点,在左侧排列它们.对于连接到这些起始节点的所有节点,将它们放在连接起始节点的右侧.对每个节点重复此操作直到结束.如果一个节点与另一个节点重叠,则移动它,并将节点链向右移,向下移动.

这对于每个隔离的链都很有用,但是当一个链的节点连接到另一个链的节点(例如连接回主干的分支)时,它通常会有一个反向连接:

我提出的这种方法似乎很粗糙.我已经阅读了一些关于Spring Force-Directed布局的内容,但它们似乎更适用于任何/所有方向的图形,而且我不完全确定如何在这里手动实现它,因为我m仅限于使用核心数学而没有其他外部库.

这不是一个常见的问题,但我并不是第一个试图弄明白的问题.我并不是要求准确的代码示例,只是为了帮助我找出一个不错的算法.

Answer 1

节点的拓扑排序（如果存在）将为您提供正确的节点显示顺序。如果两个节点不相关但排序相邻，如果您愿意，可以将它们放置在相同的 X 坐标处。

一般来说，以适当的间距绘制树是 NP 完全的（请参阅Bill Mill 的Drawing Presentable Trees中的参考资料），并且绘制图形也并不容易。

Answer 2

我没有尝试创建完美的系统，而是决定通过解决每个问题本身来强行获得一个整洁的图表，而不是阻止其产生。它很粗糙，很慢，而且远非理想，但它有效：

当它更完整时，我将在 GNU 下发布它，但现在这是它的核心： http: //www.pasteall.org/43213/python

编辑：发布：http://wiki.blender.org/index.php/Extensions :2.6/Py/Scripts/Nodes/Node_Wrangler