力导向算法

最近工作上需要实现一个关系图谱，其中图中的节点布局需要用到力导向布局，于是就对其中涉及到的力导向算法产生了兴趣，就去研究了一下。

力导向绘图 (Force-directed graph drawing)可以用于描述关系图的结点之间的关系，把结点分布到画布上合理的位置，比如描述企业之间的关系，社交网络中的人际关系等。

算法的基本原理

首先看一下一个效果图：

上图中的点的分布就是通过力导向算法计算出来，就是将节点视为同性电荷，他们之间存在斥力，这种斥力模拟库仑定律，越近斥力越大；如果两个点之间存在连线，则视为两个点之间有引力，这个引力模拟胡克定律，越远引力越大。

初始状态下我们随机放置点，然后这些点会因为引力和斥力在空间中移动，直到到达一种平衡，就形成了力导向布局。

斥力

把每个节点看做一个电荷，电荷与电荷之间存在斥力，也就是库仑力，根据库仑定律( Coulomb’s law)，电子之间的斥力可以这么计算：

$$F = k_e\frac{q_1q_2}{r^2}\overrightarrow{e}$$

我们可以假设$q_1和q_2$都是1，那么上述公式就变成了

$$F = k_e\frac{1}{r^2}\overrightarrow{e}$$

引力

一些粒子之间被一些边所牵连，这些边产生类似弹簧的胡克引力：

$$F_s = k_s(x - x_0)$$

牵制着边两端的粒子。斥力和引力不断作用，粒子在不断位移之后趋于平衡，逐渐不再发生相对位移，能量不断消耗，最终趋于零。

在引力和斥力地作用下不断地更新坐标，经过多次迭代达到一个稳定状态，收敛结束。参数和迭代次数需要调试。

计算步骤

如果要用代码去实现简化后的力导向图的布局，我们需要几个步骤。

• 设置点数据nodes, 链接数据links。
• 对点进行随机定位。
• 渲染视图
• 执行力算法计算位置，渲染视图（重复执行N次）

代码实现

其实理解了上面的流程，完全可以自己实现一个版本的力导向算法，我这里只是提供一个简单的版本，每个人实现的算法和最后的效果可能完全不同

class Node {
    constructor() {
        this.x = null;
        this.y = null;
    }
}

class Edge {
    constructor(source, target) {
        this.source = source;
        this.target = target;
    }
}

const CANVAS_WIDTH = 1000;
const CANVAS_HEIGHT = 1000;

class ForceDirected {
  constructor(n) {
    this.mNodeList = new Array(n).fill(0).map(new Node());
    this.mEdgeList = []
    this.mDxMap = [];
    this.mDyMap = [];
    this.ejectFactor = 6;
    this.condenseFactor = 3;
    for (let i = 0; i < n; i++) {
      const edgeCount = Math.random() * 8 + 1;
      for (let j = 0; j < edgeCount; j++) {
        let targetId = Math.floor(Math.random() * n);
        let edge = new Edge(i, targetId);
        this.mEdgeList.push(edge);
      }
    }

    this.coefficient = Math.sqrt(CANVAS_WIDTH * CANVAS_HEIGHT / mNodeList.length);

    const initialSize = 40.0;
    const initialX = CANVAS_WIDTH * .5;
    const initialY = CANVAS_HEIGHT * .5;
    for (let i in this.mNodeList) {
      this.mNodeList[i].x = initialX + initialSize * (Math.random() - .5);
      this.mNodeList[i].y = initialY + initialSize * (Math.random() - .5);
    }
  }

  // 计算斥力
  calculateRepulsive() {
    let distX, distY, dist;
    for (let i = 0; i < this.mNodeList.length; i++) {
      for (let j = 0; j < this.mNodeList.length; j++) {
        distX = this.mNodeList[i].x - this.mNodeList[j].x;
        distY = this.mNodeList[i].y - this.mNodeList[j].y;
        dist = Math.sqrt(distX * distX + distY * distY);
        if (dist > 0 && dist < 250) {
          this.mDxMap[i] = distX * this.ejectFactor / Math.pow(dist, 2);
          this.mDyMap[i] = distY * this.ejectFactor / Math.pow(dist, 2);
        }
      }
    }
  }

  // 计算引力
  calculateTraction() {
    let startNode, endNode;
    for (let e = 0; e < mEdgeList.length; e++) {
      const eStartID = mEdgeList[e].source;
      const eEndID = mEdgeList[e].target;
      startNode = this.mNodeList[eStartID];
      endNode = this.mNodeList[eEndID];
      let distX, distY, dist;
      distX = startNode.x - endNode.x;
      distY = startNode.y - endNode.y;
      dist = Math.sqrt(distX * distX + distY * distY);
      this.mDxMap[eStartID] = this.mDxMap[eStartID] - distX * dist / k * this.condenseFactor;
      this.mDyMap[eStartID] = this.mDyMap[eStartID] - distY * dist / k * this.condenseFactor;
      this.mDxMap[eEndID] = this.mDxMap[eEndID] + distX * dist / k * this.condenseFactor;
      this.mDyMap[eEndID] = this.mDyMap[eEndID] + distY * dist / k * this.condenseFactor;
    }
  }

  updateCoordinates() {
    let maxt = 4, maxty = 3; //Additional coefficients.
    for (let v = 0; v < mNodeList.length; v++) {
      let node = mNodeList[v];
      let dx = Math.floor(mDxMap[v]);
      let dy = Math.floor(mDyMap[v]);
  
      if (dx < -maxt) dx = -maxt;
      if (dx > maxt) dx = maxt;
      if (dy < -maxty) dy = -maxty;
      if (dy > maxty) dy = maxty;
      node.x = node.x + dx >= CANVAS_WIDTH || node.x + dx <= 0 ? node.x - dx : node.x + dx;
      node.y = node.y + dy >= CANVAS_HEIGHT || node.y + dy <= 0 ? node.y - dy : node.y + dy;
    }
  }

  update(iterateCount) {
    for (let i = 0; i < iterateCount; i++) {
      calculateRepulsive();
      calculateTraction();
      updateCoordinates();
    }
  }
}