Placing a network
A graph with no direction has no top. Stress majorization places the nodes so the page agrees with the graph — and, unlike a spring embedder, it does it the same way twice.
In the code: engine/layout/force.py
A layered layout answers one question: how far is this node from a source? That is the right question for a pipeline, a build order, a state machine. It is the wrong question for a mesh of services that call one another, and asking it anyway produces a confident answer — whichever node happened to be written first becomes the top of a hierarchy nobody claimed.
So <network> asks a different one. Not how far from the start, but how far
from each other.
Stress
Give every pair of nodes a target distance: the number of edges between them, found by breadth-first search from each node in turn. Then score a drawing by how badly it misses those targets.
stress(p) = Σ wᵢⱼ · ( ‖pᵢ − pⱼ‖ − dᵢⱼ )² over every pair i < j
dᵢⱼ is the hop count, ‖pᵢ − pⱼ‖ the distance on the page. The weight
wᵢⱼ = dᵢⱼ⁻² is what stops distant pairs shouting down near ones: without it a
pair six hops apart contributes thirty-six times the error of a pair one hop
apart for the same proportional mistake, and the drawing gets the far things
right at the cost of the near ones — which is backwards, because the near ones
are what a reader traces.
This is multidimensional scaling, borrowed. Kamada and Kawai brought it to graph drawing in 1989; the formulation above is theirs.
Majorization
Minimising that sum directly is awkward — it is not convex, and the square root inside the norm makes the derivative unpleasant near zero. SMACOF (de Leeuw, 1977 — Scaling by MAjorizing A COmplicated Function) sidesteps it with a trick that is one idea wide.
Instead of minimising the hard function, find an easy one that touches it at the
current point and sits above it everywhere else. Minimise that — which is a
weighted average, so it has a closed form — and you land somewhere the hard
function is no worse. Repeat. Gansner, Koren and North applied it to graph
drawing in 2004, and it is what Graphviz's neato runs by default.
Each pass moves every node to where its neighbours would put it:
pᵢ ← ( Σ wᵢⱼ · ( pⱼ + dᵢⱼ · unit(pᵢ − pⱼ) ) ) ÷ ( Σ wᵢⱼ ) over every j ≠ i
Read the bracket as: node j thinks node i belongs dᵢⱼ away from it, in the
direction i currently lies. Every other node votes; the weights settle it.
Why not springs
Sauvignon's constraint is unusual and it decided the algorithm. Every diagram in
the gallery is committed as SVG and has to compile back byte for byte, so a
layout that wanders between runs cannot ship. There is no import random
anywhere in the package.
A spring embedder needs a random starting placement and a cooling schedule, and its quality depends on both. Majorization needs neither: stress falls monotonically, so a fixed number of passes is "close enough" rather than "until it settles", and the starting circle is written order. The same input is the same picture, and reversing the order the nodes were written is a different input rather than a different run of the same one.
That monotonicity is not a convenience. It is the reason the technique is here at all and the spring embedders are not.
Points are not boxes
Majorization places points. Two points a comfortable distance apart are still two rectangles overlapping when one of them is wide, so a separation pass follows: any overlapping pair is pushed apart along whichever axis they overlap least, which is the smaller correction of the two and so gives up as little of the shape the stress found as it can.
It is a bound rather than a guarantee. Pairs resolve one at a time, so a long chain of overlaps takes many rounds, and a pile of coincident boxes takes more than the budget allows — eight of them want two hundred rounds and get sixty. Stopping there leaves a drawing the label gate can complain about; not stopping leaves no drawing at all.
The scale matters too. One hop is worth the room a node actually takes, averaged over the component. Points would need no such number; rectangles do, or the picture comes out the wrong size for its contents.
Pieces that are not connected
Two nodes with no path between them have no hop count, and so no distance the layout could honour. Each connected piece is laid out on its own and the pieces are set side by side — which is also the only arrangement that says plainly that they are not connected. Anything cleverer would imply a relationship the data does not have.
What it costs, and what it is not
Each pass is O(n²), and the pass count is fixed, so the whole thing is
O(passes × n²) — right for a diagram and wrong for a graph of any size. That is
the same trade <graph> makes, for the same reason.
It also finds a local minimum, not the best drawing. Stress majorization descends; where it lands depends on where it started, and it started on a circle. And it makes no attempt at crossing minimisation — a mesh has crossings, and pretending otherwise would mean trading the distances for them.