Incremental layout
Edit the graph and the parts of the drawing you did not touch stay where they were. That is the claim Dagr competes on, and this page is the evidence for it rather than the API behind it: what the stability of an incremental drawing costs, what it buys, and how both were measured. The types, the engine and the metrics themselves are on the layout pipeline page.
The stability numbers here come from a committed corpus,
packages/layout/test/sequence-stability.golden.json, produced by
layout.sequence.golden.test.ts and asserted on exactly. A change to the
pipeline that moves any of them moves the file too, so a stability regression
arrives as a diff someone can ask about rather than as a feeling.
To watch one edit do this rather than read a table of many, the
living graph demo is the same claim on screen. It edits a
32-node pipeline in front of you, one graph.batch at a time, and counts what
each edit moved off the LayoutDelta the engine answered with: three nodes
added, six moved, twenty-six of thirty-five exactly where they were, with those
twenty-six visibly not moving. It is an illustration of what is measured here
and not a measurement of its own: one graph, one seed, six edits.
Why a session and not a patch
Every other stability test in the package measures one edit. A node arrives, and the drawing before is compared with the drawing after. That is the right shape for a contract and the wrong shape for the question this page answers.
The warm start is a constraint rather than a hint: a previous layering handed to the order stage freezes the relative order of the nodes it names, so a crossing that could be removed by swapping two of them stays there with nothing to give it back. Measured over a single patch, that cost at most 1.59% in crossings, and three of six graphs came out cheaper warm than cold. A rule that gives up a fraction of a point per edit is invisible at one edit and is the whole story at eighty. Only a session can ask.
So the corpus is six scripted sessions, each a base graph and a fixed list of edits replayed one patch at a time:
| Session | Steps | Base nodes/edges | Final nodes/edges |
|---|---|---|---|
grow-tall | 16 | 240/620 | 272/684 |
prune-wide | 16 | 320/900 | 288/723 |
rewire-mid | 16 | 260/780 | 260/780 |
reparent-mid | 8 | 200/520 | 200/520 |
churn-balanced | 16 | 240/640 | 240/640 |
pattern-blocks | 12 | 180/460 | 228/508 |
rewire-mid moves an edge at a time, so nothing arrives to widen an influence
set and nothing leaves to shrink one: every node that moves moved because the
layering moved under it. churn-balanced adds four nodes and removes the same
four on the next step, so the graph is the base graph again after every second
patch. pattern-blocks adds a hub and its leaves in one patch, which is the
shape a pattern generator emits and the case where the order stage is handed a
cohort rather than a node.
The three configurations
PreparedState.previous is the only way a previous run reaches a stage, and two
of the default stages read it: the rank stage hands the previous reversed set to
the cycle breaker and checks the previous ranks against the view it is about to
rank, and the order stage holds to the previous layering. So the corpus runs one
engine three times with that channel cut in three places.
- Cold. No stage sees a previous run. Every patch is a fresh layout, which
is what a caller who throws the engine away and calls
layout()again gets. - Warm order. The order stage holds to the previous layering. The ranker starts cold, so the layers themselves are re-derived every time.
- Incremental. Every stage that reads a previous run gets one. This is what the engine does out of the box.
Same engine, same stages, same config, same tolerance, same script. The only difference between two columns is what a stage was allowed to have seen.
What it costs, and what it buys
Mean crossings across the session, and the mean distance a surviving node travelled per patch:
| Session | Crossings cold | warm order | incremental | Displacement cold | warm order | incremental |
|---|---|---|---|---|---|---|
grow-tall | 5,009 | 5,462 | 5,701 | 502.1 | 103.1 | 87.8 |
prune-wide | 14,683 | 15,741 | 15,578 | 1644.8 | 91.2 | 42.9 |
rewire-mid | 11,245 | 12,975 | 12,801 | 1039.8 | 224.2 | 137.1 |
reparent-mid | 4,840 | 4,840 | 4,840 | 0 | 0 | 0 |
churn-balanced | 5,918 | 6,178 | 6,104 | 633.9 | 176.6 | 153.8 |
pattern-blocks | 3,523 | 3,514 | 3,514 | 260.5 | 10.3 | 10.3 |
The cost is 3.1% to 13.8% in crossings, incremental against cold, on four of
the five sessions that change the graph. pattern-blocks is the fifth and comes
out cheaper warm than cold, by 0.3%. Over a single patch the same trade measured
at most 1.59%, so the honest reading is that the cost compounds: a session pays
several times what one edit suggested it would, and the largest session cost
here is roughly nine times the largest one-patch cost.
What it buys is between 4.1x and 38.4x less movement. prune-wide is the
extreme, at 1644.8 units per patch cold against 42.9 incremental, and
churn-balanced the mildest at 4.1x. The share of the drawing that moves at all
falls with it, and the relative order of the drawing stops churning entirely:
| Session | Moved share cold | incremental | Order churn cold | incremental |
|---|---|---|---|---|
grow-tall | 0.85 | 0.52 | 0.26 | 0.00 |
prune-wide | 0.96 | 0.55 | 0.44 | 0.00 |
rewire-mid | 0.97 | 0.73 | 0.40 | 0.00 |
reparent-mid | 0.00 | 0.00 | 0.00 | 0.00 |
churn-balanced | 0.97 | 0.79 | 0.36 | 0.00 |
pattern-blocks | 0.61 | 0.08 | 0.20 | 0.00 |
Order churn at exactly zero, on every session and every step, is the constraint being total rather than a metric being kind. Two nodes that shared a rank in the previous drawing are in the same relative order in the next one, always. That is the property a reader tracking a node across an edit actually relies on, and it is also the reason the crossing count has nowhere to go: the swap that would remove a crossing is the swap the constraint forbids.
The numbers here are counts and distances rather than timings, so they are the same on any machine that runs the suite. What a run costs in milliseconds is on the pipeline page, and what a relayout costs is below, each scoped to the machine it was measured on.
Two things the corpus found
Containment is not laid out. reparent-mid changes nothing but which node
contains which, and every column draws the same picture every step: zero
displacement, zero rerouting, the same 4,840 crossings. That is the correct
answer today, because no stage in the pipeline reads a parent, and it is
asserted rather than left implicit so that the day inline compound layout lands
this is the row that says so.
An edit and its exact undo do not return the drawing to where it started.
churn-balanced adds four nodes and removes the same four, so the graph is
identical at the end of every cycle. The cold and warm-order columns redraw the
base graph and hold exactly what they held at the first cycle boundary, every
number identical at every later one. The incremental column does not: at one
cycle of the eight, its held reversed set gains an edge and keeps it, and the
ranking that follows mints ten more dummy nodes which it also keeps.
That is the retention rule working rather than a leak. A previously reversed edge is held reversed while it stays a back edge, and the whole point of not re-deciding is that a drawing does not flip when a graph changes. The price is hysteresis, and nothing had measured it before this corpus. What is checked is that it settles: the session's held state takes at most two distinct values across the seven cycle boundaries it has, and every per-node map is still exactly the roster of the drawing, so nothing is retained for a node that has left.
What a relayout costs
Wall-clock milliseconds for one engine.relayout(patch) on the 10k corpus
(10,000 nodes, 40,000 edges) at the defaults, measured on an Apple M4 under Node
25.6.1 at a one-minute load average of 1.72. A cycle adds a leaf under a node in
the middle of the graph, grows that node with a nodeSize callback, shrinks it
back and removes the leaf. Each figure is a median over eleven cycles after two
warmups, so the resize column pools both size changes, 22 relayouts.
| Phase | add a leaf | remove a leaf | resize a node |
|---|---|---|---|
longest-path-rank | not run | not run | not run |
barycenter-order | 76.6ms | not run | not run |
grid-position | 19.1ms | 17.6ms | 17.9ms |
polyline-route | 25.8ms | 24.6ms | 24.5ms |
| everything else | 77.4ms | 58.5ms | 49.4ms |
| whole relayout | 202ms | 103ms | 92.3ms |
A resize runs only position and route. Neither the rank stage nor the order stage reads a size, and run again over an unchanged graph both would land where they are, so the engine positions and routes over the ranks and layers it already holds, and the answer is the one a full run gives.
So does a removed leaf, meaning a node whose one edge came in from the rank above. Ranks count up from the sources, so no other node's rank depended on it, and every layer left is part of one the engine holds, whose order the order stage's warm start would keep. The engine takes the leaf out of the held ranks and layers and positions and routes over the rest, and the answer is again the one a full run gives. It runs all four stages instead when the leaf was the only node on its rank, since the drawing then loses a layer, or when the edges reversed to break cycles would come to more than half of the edges left.
An added leaf skips the rank stage, meaning a new node whose one edge comes in from a node already drawn. It sits one rank below that node and sets no other node's rank, its edge is short, so no dummy chain changes, and with no edge out it closes no cycle, so the edges reversed to break cycles stay the ones the engine holds. The engine ranks the leaf into the held ranks and runs order, position and route over them, and the answer is the one a full run gives. Before this the rank stage took 58ms of an added leaf and the work outside the stages 167ms, measured on the same machine on 2026-11-19 UTC.
The order stage then sweeps only the leaf's layer. Every other layer is one the warm start holds whole, and a sweep over such a layer can only put back the order it already has, so the stage leaves those layers alone and never scores the gaps between two of them, which add the same crossings to every score it compares. The layers it returns are the ones a stage that sweeps every layer returns. Leaving those layers unswept took the order stage from 351ms to 128ms, each measured on the same machine on 2026-11-19 UTC before and after that change. Leaving their gaps unscored then took it from 119ms, measured that day at a load average of 1.81, to 103ms at a load average of 3.1. Putting each layer in its cohort's order by dropping members into buckets by key, rather than by a comparison sort, then took that step from about 20ms to about 4ms and the stage to 86.8ms at a load average of 1.61. Building its index with each segment written into a typed array sized up front, rather than pushed onto growing arrays, then took the stage to 75.0ms at a load average of 2.95; the stage has not changed since, and the 76.6ms the table measures it at now is within the spread between runs. What is left of it is mostly building that index, which still numbers every node and dummy by id, and its warm-start cohorts and sweeping the leaf's layer, not sweeping the held layers. A cold run of the same graph, measured in the same session, takes 648ms, and an added leaf takes 12 frames at 60 Hz, against M3.9b's budget of one; a removed leaf takes 6. The order stage is 38% of an added leaf. Skipping stages alone cannot meet that budget: "everything else", the work outside them, is about 5 frames on its own for an added leaf, and about 3 even for a resize, which skips the rank and order contract checks. It includes measuring nodes, the influence region, merging the dummy sizes, the stage contract checks, assembling the result, the delta and retaining the warm start. Measured separately on a different machine, the influence region is 7ms to 9ms for each patch kind (Ryzen 9 9900X, Node 22.22.1, 2026-11-19 UTC), down from 13ms to 17ms before it stopped reading its band from rows full of dummies. The table above was measured after that change. The stage contract checks then stopped resuming a generator once per roster member (184,222 of them on the 10k, dummies included), and the order check stopped keeping a placed set beside its roster set. On that Ryzen machine, two runs each before and after on 2026-11-20 UTC, the work outside the stages went from 166ms to 167ms down to 126ms to 128ms for an added leaf, from 113ms down to 99ms to 100ms for a removed leaf and from 95ms to 97ms down to 82ms to 83ms for a resize. The table above was measured after that change too, on 2026-11-20 UTC; on the Apple M4 the work outside the stages for an added leaf was 96.8ms before it, at a load average of 2.95, against 77.4ms after it at 1.72.
Like the pipeline page's What a run costs, which was measured on a different machine, this is a measurement and not a baseline: nothing gates on it. The test that holds this table to the committed file also checks, on the 1k corpus, which stages each patch kind runs, so a fast path that fires there without a re-measure fails it.
What is not here yet
Every relayout in the session corpus is a full pipeline run, with one exception noted below; no session resizes a node or adds or removes a single leaf on its own, so none of the paths above fires there. The stability above comes from what the stages are handed rather than from work they skip, so a structural patch other than a single leaf still costs most of a cold layout in time.
This page predicted that the incremental ranking, the stable coordinate assignment and the fast paths would each move the incremental column when they landed. All three have landed, and not one of them moved a number here. Each has a reason, and none of them is that the corpus cannot see:
- Incremental ranking checks the previous ranks rather than being seeded from them, and longest path has one answer per graph, so a warm ranking IS the cold ranking. It changes the work and cannot change the drawing.
- Stable coordinate assignment slides a finished Brandes-Koepf drawing back
onto the previous run's coordinates.
brandesKoepfPositionis not the default position stage, so nothing in this corpus is drawn by it. - The zero-stage fast path answers a patch that changes nothing the pipeline
reads from the drawing already in hand. It fires on
reparent-mid, which is the one session whose expected answer already was that nothing moves. That session is now the exception to the first sentence above: its relayouts run no stage at all.
What is still missing is most of the work the third bullet does not do. A resize and a removed leaf now run only position and route, and an added leaf skips the rank stage (see the table above), and no session in this corpus does any of those on its own. An added leaf still takes 12 frames, and bringing it inside one is what would make a small structural edit cheap in time rather than only stable in space.
The corpus does not yet carry a comparison between the current warm-start rule and a softer one that would let the transpose pass break a held pair on a strictly improving swap. That rule was measured and rejected on one-patch evidence, and the compounding above is exactly the evidence that reopens it.
Regenerating the numbers
UPDATE_GOLDEN=1 pnpm --filter @prnt/dagr-layout test layout.sequence.golden
MEASURE_COST=1 pnpm --filter @prnt/dagr-layout test layout.relayout-cost
Do it when you deliberately changed what the pipeline does and can say what moved and why. A number that changed without an intended cause is something to investigate rather than a file to refresh, and that goes for a number that improved too.