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

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以？

Answer 1

你说的是正确的.你的术语/物理学有点偏离:你所谓的质量和"k"有点混淆了最好被称为"电荷"(对于反平方律排斥)和"弹簧常数"胡克的法律吸引力.

正如对你的问题的评论回复中所指出的那样,你确实需要一些阻尼,它实际上将能量从系统中带走,否则它只会振荡将势能转化为动能并永久地回来.更糟糕的是,如果你不小心,模拟精度问题很容易导致能量无限增加,模拟"变得疯狂".

这篇维基百科文章有一些很好的伪代码,你会发现它与你的非常相似,但是上面提到了这些要点(尽管注意到即使伪代码在加速度计算中也缺少分数;请参阅页面的讨论).

您还需要考虑一下您将开始模拟的初始分布,以及您如何关注如果存在(可能)更好的全局最小值而陷入局部最小值的可能性.这些要点是相关的; 很大程度上取决于图表的拓扑结构.如果它是一棵简单的树,你可以轻松获得一个漂亮的布局.如果它有很多循环和结构......祝你好运.