图论 - 基于力的自动布局算法

Question

在开始实现之前，只是想确认一下我的理论是否正确。

常数：

• m = 顶点的质量（都相同 - 可能将其设置为节点的半径）
• k = 恒定的边缘力。
• l = 达到“能量最小状态”的边缘长度。

变量：

• d = 两个顶点之间的距离。
• cl = 边缘的当前长度。

理论： 每个顶点对每个其他顶点都有排斥力，其公式为：m / (d^2)。对于每条边缘，它展示了一个力，使得两个顶点在方向上被拉向达到“能量最小状态”；所以每个顶点受到的力为：-k * ((l - cl) / 2)。

伪代码：

until energy minimal state
   for each vertex v1
      for each vertex v2
         if v1 != v2
            v1.velocity += m / square_distance (v1, v2)
         endif
      end
   end
   for each edge e
      e.v1.velocity += -k * (delta_min_energy_len (e) / 2)
      e.v2.velocity += -k * (delta_min_energy_len (e) / 2)
   end
   for each vertex v
      v.position += (v.velocty * dampening_constant)
   end                
end

评论：那这个会起作用吗？我应该将m和k设置为多少？

- Cheetah

---

不要忘记加上某种阻尼。否则你的顶点将会永远晃动不止。 - Howard

看起来你的“对于每个边缘”循环应该除了v1之外还有一个v2的行。 - LarsH

此外，如何检测外层循环的条件“能量最小状态”已经满足？我认为需要更具体地说明。 - LarsH

谢谢您的第一条评论 - 现在已经修复了。当所有顶点的速度很小（名义上）时，达到“能量最小状态”。 - Cheetah

好的。那是达到最小能量状态的标准准则吗？似乎有时可能会由于振荡状态而无法终止，但也许这就是我们在不变得非常复杂的情况下所能期望的最好结果了。 - LarsH

也许这在您的伪代码中是隐含的，但每个加速语句 velocity += ... 都需要提供方向。我假设您将通过将加速度的大小乘以 (v1 - v2) 或 (v2 - v1) 来获得此信息。 - LarsH

Answer 1

你的方向是正确的。 你的术语/物理学有点偏差：你所谓的质量和“k”与更好称为“电荷”（对于反比平方定律斥力）和胡克定律吸引力的混淆在一起。

正如在您的问题的评论回复中指出的那样，您确实需要一些阻尼来从系统中取出能量，否则它将永远将势能转化为动能并不断地来回振荡。 更糟糕的是，模拟精度问题很容易导致能量无限增加，如果不小心，模拟就会“疯狂”。

这篇wikipedia article文章有一些不错的伪代码，你会发现它非常类似于你的代码，但解决了上述问题（尽管请注意，即使该伪代码在加速度计算中缺少除以质量的部分; 请参见页面的讨论）。

你还需要考虑一下模拟开始时的初始分布，以及如果存在一个（或许）更好的全局最小值，你对于被卡在局部最小值的可能性有多关注。这些点是相关的；很多情况取决于你的图的拓扑结构。如果它是一棵简单的树，那么你很容易得到一个漂亮的布局。如果它有很多循环和结构……祝你好运。

- timday

Answer 2

我不会为每个顶点选择相同的m。相反，我会使它与其连接的其他顶点数量成比例。这样，图形的极端部分会比高度连接的部分更快地飞离其位置。

对于k，我没有任何想法。

- Vincent Cantin