Layout Engine Internals

Layout Engine Internals

Heads-up: this is the part of the system that has changed most, and the in-repo docs/ lag it. This page documents what's actually in lib/layout.ts and lib/layout/ on main — including the stress and backbone engines and the budget system the older docs don't mention.

For the user-facing view (picking engines, the "layout simplified" note), see Layouts & Navigation.

Scene → layout → positions

Layout consumes a geometry-free scene (lib/graph/scene.ts) — node/edge identity and a signature string of every layout-affecting input. The signature is a cache key:

• Unchanged scene → reuse positions (a small LRU cache, client-side).
• Changed scene → new layout, seeded with the previous positions (LayoutOptions.previousPositions) so cards don't teleport when you re-filter or zoom. This "mental map" preservation runs through community detection, SCC ordering, and component packing, all of which are deterministic.

Off the main thread

Layout runs in a Web Worker (lib/layout.worker.ts, driven by lib/layout-client.ts):

• The worker runs runLayout(input, options) and posts back flat [id, x, y] positions + cluster boxes.
• Termination is guaranteed. If the worker hangs on a pathological input it is killed (not merely fallen back) so it can't block every future layout, and the client falls back to a synchronous grid.
• If the worker caught an engine error and fell back internally, it reports it; the client logs a layout / worker-error telemetry event so a silently-degraded layout is visible.

The engines

LayoutAlgorithm (in lib/layout.ts):

Engine	Backed by	Notes
smart	the planner (below)	Default. Clusters + picks an engine per cluster.
layered	dagre	Hierarchical; directions TD/LR/BT/RL.
tree	dagre	Tree-shaped.
radial	custom	Hub-and-spoke.
circular	custom	Ring (sized to card dimensions, no overlap).
grid	custom	Uniform — also the universal fallback.
force	d3-force	Weighted edge attraction.
stress	webcola + PivotMDS	Metric layout — see below. Not in the older docs.
backbone	custom	Dense core + leaf fringe. Not in the older docs.

Stress — the scalable metric engine

stress is a hybrid, chosen by component size:

• Dense / small (≤ ~600 nodes, ≤ ~4000 edges) → true stress majorization via webcola (SMACOF + overlap avoidance), seeded from previous positions.
• Large / sparse → PivotMDS (Brandes & Pich landmark MDS) in lib/layout/stress.ts: near-linear O(k·(V+E) + n·k²) instead of stress's O(V·E), with deterministic max-min pivot selection and fixed-seed power iteration. A work-budget guard (stressWork(...) > MAX_STRESS_WORK) drops it to grid before it gets expensive.

This is what lets the Smart layout handle thousands of nodes without dagre's blow-up.

The Smart planner

Smart doesn't run one algorithm — it builds a cluster hierarchy (by directory, or detected community) and chooses an engine per cluster from its shape (lib/layout/planner.ts chooseEngine, over lib/layout/shape.ts):

• isolates/disconnected → grid
• tree-like (high treeScore, has sources) → tree
• small + cyclic → circular
• dense core + leaves → backbone
• large cyclic component → stress
• dense or strong communities (modularity) → force
• mild cycles (fallback) → layered

For leaf clusters it can score a few candidate engines and keep the lowest-crossing result; container clusters lay out their items with a weighted Force. Supporting algorithms live alongside: community.ts (deterministic label propagation), scc.ts (iterative Tarjan), weight.ts (edge weighting), and connected-components + shelf-packing for disconnected graphs.

Edge weighting

Layout ranks relationships by importance, not count alone: relationshipWeight(kind) × log2(1 + count) (lib/layout/weight.ts). Structural ties pull hardest — extends/implements (8) and injects (6) outrank import (4), renders (3), instantiates (2), and call (1). So one inheritance edge outweighs thousands of calls when positioning.

The budget system (graceful degradation)

Heavy engines are O(V·E)-ish, so each has a node-count cap and there's a shared edge cap (lib/layout.ts):

HEAVY_COMPONENT_CAP = { stress: 6000, layered: 1200, tree: 2500, backbone: 1500, force: 1800 }
HEAVY_EDGE_CAP      = 8000

resolveEngineForBudget(requested, nodeCount, edgeCount) returns the engine to actually run plus a fallbackReason. If a (sub)graph exceeds the engine's node cap — or the edge cap (stress is exempt; PivotMDS is near-linear in edges) — it's downgraded to grid. layoutFallbackSummary aggregates those downgrades into the user-facing "layout simplified" indicator (e.g. "Stress → Grid (2 areas)").

Active work: PR #75 adds a density guard on top of the count caps — small-but-dense components (≈ >2.5 edges/node above ~32 nodes) can pin dagre's network-simplex for >60s while sailing under the node/edge caps, so layered grids them too. Track it there until merged.

Testing layout

Layout is guarded by unit tests (lib/layout.test.ts) and by the stability snapshot in bench/ (node positions for the smart & layered engines, within ±2px). A changed snapshot means a layout changed — review before updating. See Development & Building.