Force-oriented algorithm

Recently, I need to implement a relational graph in my work. The node layout in the graph needs to use force-oriented layout, so I was interested in the force-oriented algorithm involved, and I went to study it.

Force-directed graph drawings can be used to describe the relationships between nodes of a graph, distributing nodes to reasonable positions on the canvas, such as describing relationships between enterprises, interpersonal relationships in social networks, etc.

Basic principle of algorithm

Let’s first take a look at a rendering:

The distribution of the points in the above figure is calculated by the force guidance algorithm, which is to regard the nodes as the same charge, and there is a repulsive force between them. This repulsive force simulates Coulomb’s law, and the closer the repulsive force, the greater the repulsive force; if there is a connection between two points, it is regarded as an attractive force between the two points. This attractive force simulates Hooke’s law, and the farther away the attractive force is, the greater the attractive force.

In the initial state, we randomly place points, and then these points will move in space due to attractive forces and repulsive forces until a balance is reached, forming a force-oriented layout.

Repulsive force

Consider each node as an electric charge, and there is a repulsive force between the charges, which is the Coulomb force. According to Coulomb’s law, the repulsive force between electrons can be calculated as follows:

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

We can assume that $q_1 and q_2 $are both 1, then the above formula becomes

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

Attractive force

Some particles are entangled by some edges that produce a spring-like Hooker attractive force:

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

The repulsive and attractive forces continue to act, the particles tend to balance after continuous displacement, and gradually no longer have relative displacement, and the energy is continuously consumed, and finally tends to zero.

Under the action of attractive force and repulsive force, the coordinates are constantly updated, and after multiple iterations, a stable state is reached, and the convergence is over. Parameters and iterations need to be debugged.

Calculation step

If we want to use code to implement the simplified layout of the force guide diagram, we need several steps.

• Set point data nodes, link data links.
• Random positioning of points.
• Render View
• Execution algorithm calculates position, renders view (repeated N times)

Code implementation

In fact, understand the above process, you can fully implement a version of the force-oriented algorithm, I just provide a simple version here, each person to achieve the algorithm and the final effect may be completely different

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);
    }
  }

  //Calculate repulsion
  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);
        }
      }
    }
  }

  Calculate the attractive force
  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();
    }
  }
}