force-directed: springs and chargesforce-directed: springs and charges

force-directed layout is popular for one reason: you don't have to tell it anything about your graph. no hierarchy, no groups, no hints. you set up a few forces, let them run, and the shape shows up by itself. tightly connected nodes end up close together. a node that links two groups ends up between them.

this post covers how that works, the math behind it (it's small), and the ways it goes wrong.

the spring-and-charge modelthe spring-and-charge model

the idea comes from Eades in 1984, and it's pure physics:

• every node is like a magnet that pushes all other nodes away.
• every edge is like a spring that pulls its two nodes together.

run it and the two effects fight until they balance. connected nodes stay close. unconnected ones drift apart.

take four nodes in a loop: A to B, B to C, C to D, D back to A. drop them at random:

start (random):

   A             C


            B
                       D

let the forces run and they settle into a square:

after it settles:

         A ─── B
         │     │
         │     │
         D ─── C

nobody told it "draw a square". a square is simply the shape where every edge is the same length and the unconnected pairs are as far apart as they can get.

on a single node, it looks like this. A has an edge to B, and C, D, E are nearby but not connected:

              (C pushes A away)
                       ↑
                       │
   B ←──────────────── A ──────────────→ (D pushes A away)
   (the edge pulls     │
    A toward B)        │
                       ↓
              (E pushes A away)

add up the arrows, move A a small step in that direction, and repeat for every node. do that many times and the layout stops changing.

fruchterman-reingold: the version everyone usesfruchterman-reingold: the version everyone uses

Eades's original forces were fiddly to tune. in 1991, Fruchterman and Reingold replaced them with two simple formulas built around one number, k: the ideal edge length.

k = sqrt(area / n)

area is the size of the drawing, n is the number of nodes. in plain words: give each node an equal share of the space.

then the two forces, where d is the distance between two nodes:

pull along an edge:    d² / k
push between any pair: k² / d

the pull grows fast when an edge is stretched. the push grows fast when two nodes get too close. the two are exactly equal when d = k. so every edge wants to be k long.

drag the distance below and watch which force wins on each side of k:

one step by handone step by hand

two connected nodes: A at 0, B at 8. the drawing is 10 by 10, so k = sqrt(100 / 2) ≈ 7.07.

• push: 50 / 8 ≈ 6.25, apart.
• pull: 64 / 7.07 ≈ 9.05, together.
• the pull wins by 2.80, so each node moves 2.80 toward the other.

now they're only 2.40 apart, so the push wins and shoves them back. they bounce around k until something calms them down. that something is the temperature.

the cooling schedulethe cooling schedule

left alone, nodes overshoot and bounce forever. FR fixes this with a temperature t: no node can move more than t in one step.

t starts big, so early on nodes can jump far and escape bad starting spots. then t shrinks every step, so later moves get smaller and the layout settles. when t reaches zero, it's done.

watch it runwatch it run

here it is on a few small graphs. the red bar is the temperature. the ringed node shows its forces: coral arrows push, mint arrows pull. drag a node and let go to watch it settle again.

the whole loopthe whole loop

function fruchtermanReingold(nodes, edges, width, height, iterations) {
  const k = Math.sqrt((width * height) / nodes.length);
  let temperature = width;

  for (let iter = 0; iter < iterations; iter++) {
    for (const v of nodes) v.move = { x: 0, y: 0 };

    // every pair pushes apart
    for (const v of nodes) {
      for (const u of nodes) {
        if (u === v) continue;
        const dx = v.x - u.x, dy = v.y - u.y;
        const d = Math.hypot(dx, dy) || 0.001;
        v.move.x += (dx / d) * (k * k / d);
        v.move.y += (dy / d) * (k * k / d);
      }
    }

    // every edge pulls together
    for (const [a, b] of edges) {
      const dx = b.x - a.x, dy = b.y - a.y;
      const d = Math.hypot(dx, dy) || 0.001;
      const fx = (dx / d) * (d * d / k), fy = (dy / d) * (d * d / k);
      a.move.x += fx; a.move.y += fy;
      b.move.x -= fx; b.move.y -= fy;
    }

    // move each node, but never further than the temperature
    for (const v of nodes) {
      const len = Math.hypot(v.move.x, v.move.y) || 0.001;
      const step = Math.min(len, temperature);
      v.x += (v.move.x / len) * step;
      v.y += (v.move.y / len) * step;
    }

    temperature = width * (1 - (iter + 1) / iterations); // cool down
  }
}

that's the whole algorithm: push, pull, move a limited amount, cool down. 50 to 300 rounds is usually plenty for a small graph.

kamada-kawai: a different approachkamada-kawai: a different approach

Kamada and Kawai (1989) skip the simulation. they write down one number that measures how "bad" the whole layout is, then move nodes to shrink it.

the rule behind that number: two nodes that are 3 hops apart in the graph should be about 3 edge lengths apart on screen. the further the drawing is from that, the worse the score. then they fix the worst node, recompute, and repeat.

it often gives neater, more symmetric pictures on small graphs. but it first needs the hop count between every pair of nodes, which gets expensive fast. past a few hundred nodes, FR wins.

why it gets slowwhy it gets slow

the "push" step compares every node with every other node. 100 nodes means 10,000 pairs per step. 1,000 nodes means a million. 10,000 nodes means a hundred million, and that's for one step out of hundreds.

the "pull" step only looks at edges, so it stays cheap. the push is the problem. in practice, plain FR starts to crawl around 500 to 1,000 nodes.

the fix is to stop computing every pair exactly. far-away groups of nodes can be treated as one big node. that's the Barnes-Hut trick, and it's part 2.

how it goes wronghow it goes wrong

two runs, two pictures. there's more than one shape the layout can settle into, and which one you get depends on the random starting positions. both are valid, they just look different. if you need the same picture every time, use a fixed random seed. d3-force does this for you.

tiny differences between runs, even with the same seed. if nodes are processed in a different order (for example, in parallel), rounding adds up differently. always process nodes in the same order.

some shapes don't settle well:

• graphs where everything connects to everything wander around without settling.
• grids have many equally good shapes, so the layout can flip between them. try "grid" with a few seeds in the simulator above.
• long chains can run out of temperature before they straighten. more rounds help.

a common fix for bad starts: instead of random positions, start from a quick math-based layout (spectral, part 5), so nodes begin roughly in the right place.

reading the source: d3-forcereading the source: d3-force

d3-force (at commit c3e73cf6) is a clean real-world version. it's a bit different from textbook FR. here is its main loop:

function tick(iterations) {
  var i, n = nodes.length, node;

  if (iterations === undefined) iterations = 1;

  for (var k = 0; k < iterations; ++k) {
    alpha += (alphaTarget - alpha) * alphaDecay;

    forces.forEach(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;
    }
  }

  return simulation;
}

three things to notice:

• alpha is d3's temperature. it shrinks a little every step and the simulation stops after about 300 steps. every force is scaled by it, so forces fade as it cools.
• nodes have velocity and friction. textbook FR moves nodes directly. d3 keeps a speed for each node and slows it down by 40% each step, which makes the motion smoother.
• fx and fy pin a node in place. that's how you drag or fix nodes in d3.

and here is the spring, the "pull" along each edge:

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

it measures how far each edge is from its target length and nudges both ends to fix it, scaled by alpha. two differences from FR:

• the target length is a fixed 30 pixels by default, not k. d3 is built for interactive pages, where the drawing size isn't known up front.
• bias splits the nudge by how connected each end is. a busy hub node moves less, which stops it from wobbling.

jiggle handles two nodes sitting on exactly the same spot by nudging them apart randomly.

papers to read nextpapers to read next

Eades (1984), "A Heuristic for Graph Drawing." the original spring model. hard to find online.

Fruchterman and Reingold (1991), "Graph Drawing by Force-Directed Placement." the algorithm this post is about. free PDF. its explanation of k is the clearest one around.

Kamada and Kawai (1989), "An algorithm for drawing general undirected graphs." the "score and fix" alternative. short, and good to read next to FR.

next: part 2 makes this fast on big graphs, with the Barnes-Hut trick and multilevel layout.