在这篇文章中，我希望整理力导图的建模基础，为以后的改进做准备。选取的文章是 Graph Drawing by Force-directed Placement。

# 概述

力导图 (force-directed graph) 是无向图的平面布局方式。在力导图中，顶点建模为质点，质点间力的大小根据图中边的连接确定，当整个物理模型在力的作用下达到平衡，就完成了力导图的绘制。

下面，我们假设力导图所对应的图$G(V,E)$ 是一个无边权的无向图。

力导图的绘制原则可以概括为以下几点：

1. 可以在图中清晰地区分每一个点；
2. 让边的交叉最小；
3. 让边的长度尽量相同；
4. 可以反映图中固有的对称性；
5. 与图的表示一致。

# 力建模

# 引力和斥力

力导图中存在引力 (attractive force) 和斥力 (repulsive forces)，其中引力在有边相连的顶点间存在，而斥力在所有的顶点间都存在。于是引力的数量是$\Theta(V)$，而斥力的数量是$\Theta(V^2)$.

# 理想距离

这样，我们可以对相邻顶点给出一个良好的建模，但对于不相邻的顶点，建模仍然不能给出很好的描述。于是 Kamada 与 Kawai 引入了理想距离 (ideal distance) 的概念：非相邻顶点间的理想距离与两点间的最短路长度成正比。

于是，计算布局可以转化成求

$$\sum_{1\leq i<j\leq |V|}k_{ij}(|\boldsymbol{p}_i-\boldsymbol{p}_j|-l_{ij})^2$$

的最小值。

其中$\boldsymbol{p}_i$ 是顶点$v_i$ 的位置，$k_{ij}$ 是$v_i$ 和$v_j$ 之间的弹性系数，$l_{ij}$ 是$v_i$ 和$v_j$ 之间的理想距离。