d3 / d3-force

Force-directed graph layout using velocity Verlet integration.
https://d3js.org/d3-force
ISC License
1.81k stars 376 forks source link

Iterative-Relaxation in d3.forceLink #193

Open gvarnavi opened 3 years ago

gvarnavi commented 3 years ago

Initially posted as vasturiano/d3-force-registry#8, was prompted to also post this here for broader visibility.

The documentation suggests d3.forceLink does the following (emphasis added):

The strength of the force is proportional to the difference between the linked nodes’ distance and the target distance, similar to a spring force.

Unfortunately, this might be misleading as d3.forceLink actually performs iterative relaxation. The responsible lines in the source code are:

        x = target.x + target.vx - source.x - source.vx || jiggle(random);
        y = target.y + target.vy - source.y - source.vy || jiggle(random);

Note the link distance is specified by 'peeking ahead' to the anticipated position of the node ⟨x + vx,y + vy⟩.

This has implications in energy-conservation, e.g. the two pendulum based blocks here (1 2) and in the examples in this notebook, despite all the examples explicitly specifying 0 alphaDecay and velocityDecay.

  const sim = d3.forceSimulation(nodes)
  .force("link", d3.forceLink(edges).distance(1))
  .alphaDecay(0)
  .velocityDecay(0);

Perhaps the documentation should alert users to this? Alternatively, and since a change away from iterative relaxation would render the iterations option nonsensical, the function could handle iterations(0) as a special case doing the following instead?

        x = target.x - source.x  || jiggle(random);
        y = target.y - source.y  || jiggle(random);