Force-directed算法(1)——Fruchterman-Reingold

Graph drawing即根据顶点和边的拓扑关系，将这张图展现出来。很明显，表现的形式种类是非常多的，如果精确到每个顶点的座标，那么方案有无穷多种。Graph drawing 目标是画出一张美观的图的布局来。美是个见仁见智的概念，何谓美？“每个本质在于旺盛的生命力，美的形象能够感染人的情感和鼓舞人心”，展现出来的图是否美每个人的看法可能都不一样，但有一些通用的要素是大家一般共同认可的，比如边的两端不能靠得太近也不能离得太远，相交边的数目要尽量少，有对称性等等。

Graph drawing的应用大家应该不陌生，常用的工具Graphviz就是这个领域一款成熟的开源软件。

布局算法中一类通用、扩展性好、易于实现的方法是 force-directed drawing algorithm。这类算法在 William T. Tutte. How to draw a graph. Proc. London Math. Society, 13(52):743–768, 1963. 时已经有一个雏形，
Eades, Peter (1984). “A Heuristic for Graph Drawing”. Congressus Numerantium 42 (11): 149–160. 中加入了弹簧的因素，force-directed算法就成型了。

Fruchterman-Reingold算法

下面讨论Fruchterman-Reingold算法，每个顶点在展现的图中表现为一个质点或者球(下面为方便期间牺牲严谨性称之为顶点)，任意两点间有斥力，有边关连的两点间有引力，引力可以想像成由顶点间的弹簧提供的，也就是说每一条边都表示一根弹簧。精确地，引力：

$f_a(d) = d^2/k$

$f_r(d) = -k^2/d$。

另外假定理想状况下所有画出来的边的长度都是确定的，上式中的 $k$ 就是描述边最优长度的常数，$d$ 是两点间距，可以取每个顶点平均分得的画布面积的算数平方根的常数倍。

算法初始时给每个顶点分配一个随机位置(可以组成圆形，可以是网格，也可以是其他布局算法的输出结果，但不能排在一条直线上(想一想为什么))，核心是个迭代过程，计算出所有点对间的斥力，再对于每个顶点，考虑和它关连的弹簧对它产生的引力。每一轮迭代枚举每个顶点，根据它受到的合力向量让它的位置发生改变。当所有顶点位置不发生改变或者迭代次数超过预设的某个阈值后算法结束。

伪代码如下：

f_a(d) = \d -> d^2 / k # attractive force
f_r(d) = \d -> k^2 / d # repulsive force
for i in [0..iterations)
  u.displacement = zero vector
  # regard repulsive forces
  for (u, v) in E
    d = u.pos - v.pos // vector
    u.displacement += d / |d| * f_r(|d|)
  # regard attractive forces
  for (u, v) in E
    d = u.pos - v.pos
    u.displacement += d / |d| * f_a(|d|)
    v.displacement -= d / |d| * f_a(|d|)
  # tune positions
  for u in V
    u.pos += u.displacement

让顶点位置发生改变的时候可以用上类似模拟退火算法中的温度参数，限制位置的改变量。最后还要注意放缩布局以适应画布。

一轮迭代的时间复杂度为：$O(n^2+m)$，其中 $n$ 和 $m$ 分别为点数和边数。其中 $O(n^2)$ 的斥力计算是可以优化的，方法类似 n-body 问题中的 Barnes-Hut simulation，即把遥远顶点团的斥力合力视作顶点团质心处的一个质点，可以用quad-tree、k-d tree之类数据结构优化。

注意到斥力的引入的一个缘由是防止坍塌到一点这种退化情况发生，所以斥力其实是够用就好的，所以可以设置一个和 $k$ 相关的常数 $R$，直接忽略距离超过 $R$ 的顶点。所以类似 n-body 问题，还可以用 spatial hashing 等方法优化。

执行脚本：

生成8*8的网格 /tmp/i，采用 von Neumann neighborhood。

执行scripts/gen-svg.rb -i 2000 < /tmp/i | display svg:-迭代2000次计算处这样一张图：

在github上