How to Build a Force-Directed Graph with D3.js: From Theory to Code

Introduction

D3.js is a web‑standard based JavaScript visualization library that uses SVG, Canvas and HTML for data visualisation. Graph layout algorithms organise scattered node‑link data into clear, aesthetically pleasing structures, such as tree or DAG layouts.

Different graph layouts serve different scenarios; for example, a tree layout or a DAG layout (directed acyclic graph) is suitable for workflow representations.

In a concentric‑circle layout, nodes are sorted by degree, placing the highest‑degree node at the centre and decreasing outward, forming concentric circles.

A force‑directed layout reduces node overlap by simulating repulsive forces; the implementation is based on physical theory, modelling nodes as atoms that interact until reaching equilibrium, known as a force‑directed graph .

Approach

The system can be decomposed into two entities and one factor: nodes, links, and forces. The d3‑force implementation follows the classic Fruchterman‑Reingold algorithm: compute repulsive forces between nodes, attractive forces along links, derive node velocities, and use a simulated‑annealing decay to reach stability.

Demo link: https://jsfiddle.net/smallstars/h8y6e031/51/

d3‑force Principles

Node Processing

Initialize Nodes

Nodes are imported into D3 and pre‑processed with a given radius and angle to arrange them in a circle.

// d3-force/simulation.js
var initialRadius = 10,
    initialAngle = Math.PI * (3 - Math.sqrt(5));

function initializeNodes() {
    for (var i = 0, n = nodes.length, node; i < n; ++i) {
        node = nodes[i], node.index = i;
        if (node.fx != null) node.x = node.fx;
        if (node.fy != null) node.y = node.fy;
        // initial position
        if (isNaN(node.x) || isNaN(node.y)) {
            var radius = initialRadius * Math.sqrt(0.5 + i),
                angle = i * initialAngle;
            node.x = radius * Math.cos(angle);
            node.y = radius * Math.sin(angle);
        }
        // vx, vy are velocities
        if (isNaN(node.vx) || isNaN(node.vy)) {
            node.vx = node.vy = 0;
        }
    }
}

Build Quad‑Tree

Quad‑Tree (quad‑tree)

A quad‑tree facilitates collision detection by recursively subdividing 2‑D space into four quadrants, each node having up to four children.

When inserting nodes, four cases are considered: empty tree, empty quadrant, coincident coordinates without an array index (create array index and split), and coincident coordinates with an array index (directly attach).

// d3-force/collide.js
for (var k = 0; k < iterations; ++k) {
  // build quad‑tree
  tree = quadtree(nodes, x, y).visitAfter(prepare);
  for (i = 0; i < n; ++i) {
    node = nodes[i];
    ri = radii[node.index], ri2 = ri * ri;
    xi = node.x + node.vx;
    yi = node.y + node.vy;
    tree.visit(apply);
  }
}

// d3-quadtree/add.js
function add(tree, x, y, d) {
  if (isNaN(x) || isNaN(y)) return tree; // ignore invalid points
  var parent,
      node = tree._root,
      leaf = {data: d},
      x0 = tree._x0,
      y0 = tree._y0,
      x1 = tree._x1,
      y1 = tree._y1,
      xm, ym, xp, yp, right, bottom, i, j;

  // case1: empty tree
  if (!node) return tree._root = leaf, tree;

  // descend to leaf
  while (node.length) {
    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
    if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
    if (parent = node, !(node = node[i = bottom << 1 | right])) return parent[i] = leaf, tree;
  }

  // case4: coincident point
  xp = +tree._x.call(null, node.data);
  yp = +tree._y.call(null, node.data);
  if (x === xp && y === yp) return leaf.next = node, parent ? parent[i] = leaf : tree._root = leaf, tree;

  // case3: split until separate quadrants
  do {
    parent = parent ? parent[i] = new Array(4) : tree._root = new Array(4);
    if (right = x >= (xm = (x0 + x1) / 2)) x0 = xm; else x1 = xm;
    if (bottom = y >= (ym = (y0 + y1) / 2)) y0 = ym; else y1 = ym;
  } while ((i = bottom << 1 | right) === (j = (yp >= ym) << 1 | (xp >= xm)));
  return parent[j] = node, parent[i] = leaf, tree;
}

Optimized Repulsion

The core repulsive force is the electrostatic charge force. Naïvely summing forces from all other nodes yields O(N²) complexity; using the Barnes‑Hut approximation reduces it to O(N log N).

Aggregate Forces

Barnes‑Hut groups distant nodes into a single quad, with accuracy controlled by the theta parameter, and the Velocity‑Verlet integrator updates velocities.

// d3-force/manyBody.js
var distanceMin2 = 1,
    distanceMax2 = Infinity,
    theta2 = 0.81;

function apply(quad, x1, _, x2) {
  if (!quad.value) return true;

  var x = quad.x - node.x,
      y = quad.y - node.y,
      w = x2 - x1,
      l = x * x + y * y;

  // Barnes‑Hut condition
  if (w * w / theta2 < l) {
    if (l < distanceMax2) {
      if (x === 0) x = jiggle(random), l += x * x;
      if (y === 0) y = jiggle(random), l += y * y;
      if (l < distanceMin2) l = Math.sqrt(distanceMin2 * l);
      node.vx += x * quad.value * alpha / l;
      node.vy += y * quad.value * alpha / l;
    }
    return true;
  }

  // If quad has a single node
  if (quad.length || l >= distanceMax2) return;

  // Exclude self‑interaction
  if (quad.data !== node || quad.next) {
    if (x === 0) x = jiggle(random), l += x * x;
    if (y === 0) y = jiggle(random), l += y * y;
    if (l < distanceMin2) l = Math.sqrt(distanceMin2 * l);
  }

  do if (quad.data !== node) {
    w = strengths[quad.data.index] * alpha / l;
    node.vx += x * w;
    node.vy += y * w;
  } while (quad = quad.next);
}

Link Forces

Links are initialised by computing node degrees and the proportion of each edge’s contribution to its source/target degree. The default link distance is 30 and strength is 1, reducing attraction for high‑degree nodes.

// d3-force/link.js
function force(alpha) {
  for (var k = 0, n = links.length; k < iterations; ++k) {
    for (var i = 0, link, source, target, x, y, l, b; i < n; ++i) {
      link = links[i], source = link.source, target = link.target;
      x = target.x + target.vx - source.x - source.vx || jiggle(random);
      y = target.y + target.vy - source.y - source.vy || jiggle(random);
      l = Math.sqrt(x * x + y * y);
      l = (l - distances[i]) / l * alpha * strengths[i];
      x *= l, y *= l;
      target.vx -= x * (b = bias[i]);
      target.vy -= y * b;
      source.vx += x * (b = 1 - b);
      source.vy += y * b;
    }
  }
}

Simulation Loop

The simulation repeatedly applies forces, decays the alpha parameter, and updates node positions until alpha falls below a threshold, achieving a stable layout.

// d3-force/simulation.js
var simulation,
    alpha = 1,
    alphaMin = 0.001,
    alphaDecay = 1 - Math.pow(alphaMin, 1 / 300),
    alphaTarget = 0,
    velocityDecay = 0.6,
    stepper = timer(step),
    event = dispatch("tick", "end");

function step() {
  tick();
  event.call("tick", simulation);
  if (alpha < alphaMin) {
    stepper.stop();
    event.call("end", simulation);
  }
}

function tick() {
  alpha += (alphaTarget - alpha) * alphaDecay;
  forces.each(function(force) { force(alpha); });
  for (i = 0; i < n; ++i) {
    node = nodes[i];
    if (node.fx == null) node.x += node.vx *= velocityDecay;
    else node.x = node.fx, node.vx = 0;
    if (node.fy == null) node.y += node.vy *= velocityDecay;
    else node.y = node.fy, node.vy = 0;
  }
}

Practical Example

Demo: React‑d3js Code: https://github.com/SmaIIstars/react-demo/blob/master/src/pages/d3-force/index.tsx

Common Issues

Complex SVG content – use foreignObject nodes to embed XML elements.

Too many iteration steps causing UI lag – employ React.memo and useCallback to minimise unnecessary calculations.

Node overlap – increase repulsive force and link length, though complete avoidance may be impossible in limited space.

Excessive nodes exceeding canvas – adapt canvas size to viewport and enable zoom/pan for full view.

References

GitHub – d3/d3-force: Force‑directed graph layout using velocity Verlet integration.

D3.js force‑directed graph theory documentation.