Functions A–S

Import these from @grafloria/engine.

Functions

analyseGraphShape

ts
Copy
function analyseGraphShape(nodes: NodeModel[], links: LinkModel[]): GraphShape

assessLabelClearance

Would this layout's edge labels sit on top of a node?

Requirement 2 as a measurement. We are NOT placing labels here — the renderer's edge optimizer does collision-aware placement at render time, and duplicating it would be the exact mistake the card warns against. We ask the cheaper question a LAYOUT can answer: if the label sat at its natural home (the midpoint of the route the engine computed), would it land on a node? If yes, layout has not left the optimizer enough room, and this layout is worse than one that did.

A layout with no labels is vacuously perfect.

ts
Copy
function assessLabelClearance(
  nodes: NodeModel[],
  links: LinkModel[],
  result: LayoutResult
): LabelClearanceResult

assessPortRespect

Does each edge actually leave (and enter) in the direction its port faces?

This is requirement 1 of the card as a measurement: "an edge leaving a right port should not require the layout to place the target to the left". We check the sign of the displacement along the port's facing axis. A right port whose target sits to the left scores a violation.

Only AUTHOR-DECLARED ports are judged — the four auto-created default ports carry no authorial intent, so an edge through them can go anywhere (see port-label-bridge.ts). A graph with no declared ports is vacuously perfect, which is the correct answer: there is nothing to respect.

ts
Copy
function assessPortRespect(
  nodes: NodeModel[],
  links: LinkModel[],
  portInfos?: PortInfo[]
): PortRespectResult

autoSelectLayout

Run the bake-off and keep the best layout.

IMPORTANT — this MUTATES node positions while it works: each candidate has to be applied to the model before its quality can be measured (crossings are a property of a drawn graph, not of a plan). The winner's positions are re-applied at the end, so the model always lands on the layout we chose, never on the last one we happened to try. DiagramEngine.layout() then commits them through setPosition() as usual.

ts
Copy
async function autoSelectLayout(
  diagram: DiagramModel,
  registry: LayoutRegistry,
  options: UnifiedLayoutOptions = {}
): Promise<AutoLayoutResult>

buildCandidates

The candidate pool, in a FIXED order.

Auto-tuning lives here too: a candidate is an algorithm PLUS its knobs, so dagre TB and dagre LR compete as separate candidates and the better direction simply wins on score. That is the whole of "auto-tune" — no separate tuning pass, just more candidates in the bake-off.

ts
Copy
function buildCandidates(shape: GraphShape, registry: LayoutRegistry): LayoutCandidate[]

circularLayout

Every node on one ring.

Nodes are ordered by a BFS from the lowest-id node rather than by id, because a circle's readability is entirely about edge crossings and BFS order puts neighbours next to each other. (Ordering by id would be equally deterministic and much uglier — an arbitrary permutation guarantees chords across the whole circle.)

The radius is derived from the nodes' own footprints, so a circular layout of 40 nodes does not stack them on top of each other the way a fixed radius does.

ts
Copy
function circularLayout(
  nodes: NodeModel[],
  links: LinkModel[],
  options: CircularLayoutOptions = {}
): LayoutResult

countBends

Total bend count across the routes the layout engine computed.

Bends are one of the four measures the card names, and they only became measurable once the adapters stopped discarding their routing output. A layout whose edges need fewer corners is easier to follow.

Returns undefined when the engine reported no routes — an ABSENT measurement, not a zero. Scoring "0 bends" for an engine that simply never told us would hand it a perfect score for saying nothing, which is how a metric quietly becomes a lie.

ts
Copy
function countBends(result: LayoutResult): number | undefined

createArchitectureLayout

architecture — a composition, not a ranking: regions on a grid, boxes sized to their words and aligned in rows, lines straight where boxes line up, bends in the gutters. It writes sizes, zone frames, anchors and bends as well as positions, so it runs inline (no adapter: nothing to ship to a worker) and owns its containers.

ts
Copy
function createArchitectureLayout(): RegisteredLayout

createAutoLayout

The auto-selecting layout, as a registry engine.

It is registered under a name like any other layout — deliberately. It takes the registry it lives in so its candidate pool is whatever is actually registered, including layouts an extension host added after start-up.

ts
Copy
function createAutoLayout(registry: LayoutRegistry): RegisteredLayout

createBuiltInLayoutAdapters

The layouts that ship in the box.

ELK is included even though it resolves asynchronously; the adapter already handles that.

ts
Copy
function createBuiltInLayoutAdapters(): LayoutAdapter[]

createBuiltInLayoutFactories

The same built-ins, as FACTORIES — construct one only when it is asked for.

It is a crash fix that only a live run could have found. Constructing every adapter up-front means constructing ELK, and new ELKLayoutAdapter() calls new ElkConstructor(), which tries to spawn elkjs's OWN nested Worker. Inside a Web Worker that throws _Worker is not a constructor — so the layout worker died on the line that started it, before it had read a single message, and every request to it hung forever.

Nothing caught it because in Node (where the unit tests live) elkjs constructs happily. It reproduced the instant a real Worker ran in a real browser.

Laziness makes the worker pay only for the algorithm actually requested, so asking for force no longer detonates on ELK's behalf.

ts
Copy
function createBuiltInLayoutFactories(): Map<string, () => LayoutAdapter>

createDefaultLayoutRegistry

The registry engine.layout() runs against.

Registration order is the override order, and it is deliberate:

force appears in both and the portfolio's wins, because it adds component packing and the shared options vocabulary: the difference between "we expose a force adapter" and "force is a first-class layout"; 3. LAYERED (Cards 1 & 5) — our own Sugiyama. The only engine that honours semantic constraints DURING ranking and ordering, which is why the mental-map/incremental path names it explicitly; 4. AUTO — the scored bake-off. Registered last because it takes the registry, so its candidate pool is whatever is actually in it — including layered, and including anything an extension host adds after start-up.

ts
Copy
function createDefaultLayoutRegistry(): LayoutRegistry

createLayout

Turn a raw graph-layout function into a registered layout.

1. CANONICAL INPUT ORDER — sorted by id, so the same graph laid out after a save/load round-trip produces the same coordinates.
2. COMPONENT PACKING — a disconnected graph is split, laid out component by component, and the boxes are packed. Implemented ONCE, here, rather than five times in five algorithms. It is a no-op for a connected graph, so it cannot regress an existing layout.

ts
Copy
function createLayout(name: string, fn: GraphLayoutFn): RegisteredLayout

createLayoutRng

mulberry32 — a small, fast, well-behaved 32-bit PRNG.

ts
Copy
function createLayoutRng(seed: number = DEFAULT_LAYOUT_SEED): LayoutRng

createPortfolioLayouts

ts
Copy
function createPortfolioLayouts(): RegisteredLayout[]

declaredPorts

Ports the author actually declared — the ones that may constrain a layout.

ts
Copy
function declaredPorts(node: NodeModel): PortModel[]

deriveLabelBoxes

Every label on a link, sized. Empty for the common unlabelled link.

ts
Copy
function deriveLabelBoxes(link: LinkModel): LabelBox[]

derivePortInfos

Only DECLARED ports are emitted (see the file header).

ts
Copy
function derivePortInfos(nodes: NodeModel[]): PortInfo[]

estimateLabelBox

The estimated content box of a single edge label, including its padding.

ts
Copy
function estimateLabelBox(label: LinkLabel, linkId = ''): LabelBox

estimateLayering

ts
Copy
function estimateLayering(nodes: NodeModel[], links: LinkModel[]): LayeringEstimate

findConnectedComponents

Split a graph into connected components.

Connectivity is UNDIRECTED — an edge joins its endpoints regardless of which way it points. (A tree whose edges all point away from the root is still one component; treating edges as directed would shatter it into leaves.)

Deterministic: nodes are visited in id order and each node's neighbours are visited in id order, so the components — and the order they come back in — depend only on the graph, never on insertion order.

ts
Copy
function findConnectedComponents(
  nodes: readonly NodeModel[],
  links: readonly LinkModel[]
): GraphComponent[]

forceLayout

ts
Copy
function forceLayout(
  nodes: NodeModel[],
  links: LinkModel[],
  options: UnifiedLayoutOptions = {}
): Promise<LayoutResult>

fromAdapter

Wrap a legacy LayoutAdapter (dagre/elk/force/spectral/community) as a registry engine.

This is the adaptor that finally makes the orphaned stack reachable. It also does the two things the old path never did:

1. CANONICAL INPUT ORDER — nodes and links are sorted by id before they reach the algorithm. A seeded PRNG alone does not give reproducibility: map iteration follows insertion order, so an authored diagram and the same diagram loaded from JSON feed the algorithm in different orders and diverge even with the same seed.

2. OPTION NORMALISATION — direction/nodeSpacing/rankSpacing are translated into whatever the adapter calls them.

ts
Copy
function fromAdapter(adapter: LayoutAdapter): RegisteredLayout

gridLayout

Row-major grid. Ignores links entirely — that is the point: a grid is what you reach for when the edges are NOT the story (a palette of components, a set of unconnected cards).

direction chooses the FILL ORDER of the same grid, not a different grid: 'TB' fills left-to-right then down, 'LR' fills top-to-bottom then across, 'BT'/'RL' mirror those.

ts
Copy
function gridLayout(
  nodes: NodeModel[],
  _links: LinkModel[],
  options: GridLayoutPortfolioOptions = {}
): LayoutResult

hasDeclaredPorts

Does this node carry author-declared ports? If not, layout may place it freely and route through whichever of the four default sides suits the router.

ts
Copy
function hasDeclaredPorts(node: NodeModel): boolean

inStableOrder

Deterministic order for a set of entities.

The second half of reproducibility, and the half that is easy to forget: a seeded PRNG only helps if the graph is CONSUMED in a stable order. Node maps iterate in insertion order, which differs between an authored diagram and the same diagram loaded from JSON — so two "identical" graphs could feed the same seeded generator in different orders and still diverge.

Sorting by id makes the input canonical, which is what actually makes the layout idempotent across a save/load round-trip.

ts
Copy
function inStableOrder<T extends { id: string }>(items: readonly T[]): T[]

isDefaultPort

Was this port invented by NodeModel.initializeDefaultPorts() rather than declared by the author?

The model marks them (setMetadata('default', true)), which is the only trustworthy signal — explicitSide is TRUE even for the default ports (they are constructed with side:, and the PortModel constructor sets the flag), so explicitSide cannot be used to tell an authored port from an invented one. That trap is exactly why this helper exists instead of an inline check.

ts
Copy
function isDefaultPort(port: PortModel): boolean

isSteppable

Can this adapter be pre-empted mid-run?

ts
Copy
function isSteppable(
  adapter: LayoutAdapter
): adapter is SteppableLayoutAdapter

layoutArea

The area of the layout's bounding box, in px². Smaller is tighter.

ts
Copy
function layoutArea(result: LayoutResult): number

layoutWithComponentPacking

Run a layout with component packing.

The wrapper every registered layout goes through. See the header: for a CONNECTED graph this is a straight delegation (packing a single component is the identity), so it cannot regress anything; for a disconnected one it is the difference between a tidy row of trees and a pile.

ts
Copy
async function layoutWithComponentPacking(
  name: string,
  fn: GraphLayoutFn,
  nodes: readonly NodeModel[],
  links: readonly LinkModel[],
  options: UnifiedLayoutOptions = {}
): Promise<LayoutResult>

linkLabelBox

The single box that must fit on a link: the union of its labels' boxes.

ts
Copy
function linkLabelBox(link: LinkModel): LabelBox | undefined

nodeSize

A node's box, with the same defaults every layout in the portfolio uses.

ts
Copy
function nodeSize(node: NodeModel): { width: number; height: number }

packAdapter

Component-packing wrapper, preserving the algorithm underneath.

Object.create, not a spread: spreading a class instance copies only its OWN properties, so step()/snapshot() — which live on the prototype — vanish, isSteppable() goes false, and a long-running algorithm silently stops being cancellable. Delegating through the prototype keeps it whole and overrides only apply, which is the one thing packing needs to intercept.

ts
Copy
function packAdapter(adapter: LayoutAdapter): LayoutAdapter

packBoxes

Shelf packing, first-fit-decreasing-height.

Returns the top-left OFFSET for every box. Boxes are laid left-to-right into a shelf; when the next box would overflow the target width a new shelf opens below the tallest box on the current one.

ts
Copy
function packBoxes(
  boxes: readonly PackBox[],
  options: PackingOptions = {}
): Map<string, { x: number; y: number }>

pickEngineForScale

Pick the engine(s) for a graph too large to bake off, from its STRUCTURE.

Every branch below is backed by a measurement in layout-auto-select.perf.spec.ts (times on the dev machine, generous CI caps in the spec):

tree → portfolio tree: 19ms at n=2000 (vs dagre 702ms, layered 5.3s) DAG, narrow → layered: 156ms at 900-mesh, 479ms at 2025-mesh, 132ms at a 2,000-deep chain — width is what hurts it, and narrow ranks are exactly where dagre's depth pathology lives. DAG, wide+shallow → dagre: 1.3s at a 2,000-node sparse DAG whose ~1,000-wide ranks are what kill layered. DAG, wide+deep → elk layered: the moderate-everywhere engine. cyclic → force: completes in well under a second at this scale; hierarchical engines would first have to break the cycles.

Declared ports bump ELK (the only port-aware candidate) to the front for hierarchical graphs — at this scale we cannot afford to MEASURE port respect across a whole field, so we pick the engine built to honour it.

Returns undefined when none of the preferred engines is registered; the caller then falls back to the (gated) bake-off rather than failing.

ts
Copy
function pickEngineForScale(
  shape: GraphShape,
  nodes: NodeModel[],
  links: LinkModel[],
  registry: LayoutRegistry
): ScalePlan | undefined

pickRoot

Choose the node a tree hangs from — or a radial layout centres on.

SOURCE FIRST (in-degree 0), hub second (highest degree).

hub → mid1 → leaf1, leaf2 hub → mid2 → leaf3

the CEO ('hub') has degree 2 and the middle manager ('mid1') has degree 3. A pure highest-degree rule centres the picture on the middle manager and hangs the CEO off the side — the org chart drawn upside down. Sources win; the degree rule is the fallback for a graph that HAS no source (a cycle, an undirected network), which is exactly where "the hub" is the right answer.

Every tie breaks on the lowest id, so the root never depends on insertion order.

ts
Copy
function pickRoot(
  ordered: readonly NodeModel[],
  inDegree: Map<string, number>,
  degree: Map<string, number>,
  rootId?: string
): string

radialLayout

Concentric rings by BFS depth from a hub.

The wedge allocation is what makes it readable: each subtree gets an angular slice PROPORTIONAL TO ITS LEAF COUNT, so a bushy branch is not crammed into the same wedge as a single leaf. That is the classic radial-tree construction, and it is crossing-free for trees.

Ring radii are grown to fit — a ring is pushed outward if the nodes on it would not otherwise fit around its circumference, which is the failure mode of every "radius = depth * constant" radial layout at depth 3 and beyond.

ts
Copy
function radialLayout(
  nodes: NodeModel[],
  links: LinkModel[],
  options: RadialLayoutOptions = {}
): LayoutResult

removeOverlaps

Separate overlapping nodes, in place, and return the corrected positions.

Deterministic: boxes are swept in (x, id) order, so the result is a pure function of the input positions — never of a map's iteration order.

Returns the same Map instance for convenience.

ts
Copy
function removeOverlaps(
  nodes: readonly NodeModel[],
  positions: Map<string, { x: number; y: number }>,
  options: OverlapRemovalOptions = {}
): Map<string, { x: number; y: number }>

reservedLabelSpace

The space every labelled edge needs, as one summary — what a layout engine that cannot take per-edge label boxes (force, spectral, …) uses to inflate its spacing so labels have somewhere to live.

ts
Copy
function reservedLabelSpace(links: LinkModel[]): { width: number; height: number }

resolvePortConstraint

ts
Copy
function resolvePortConstraint(
  node: NodeModel,
  mode: PortConstraintMode = 'auto'
): ElkPortConstraint

reviveGraph

Rebuild live models from the wire format, on whichever thread we landed on.

The revived models are THROWAWAY: the algorithm mutates them, we read the positions out of the result, and the engine commits those positions onto the REAL nodes via setPosition() so the spatial index and the routing obstacle map see the move. Nothing that happens to these copies escapes.

ts
Copy
function reviveGraph(graph: LayoutGraph): {
  nodes: NodeModel[];
  links: LinkModel[];
}

runLayout

Run a named layout against a diagram and COMMIT the result.

The single place positions are written back, shared by DiagramEngine.layout() and by the preset applicator. setPosition() — never a raw write to node.position — because the spatial index, the routing obstacle map and the renderer all hang off the change event it emits.

ts
Copy
async function runLayout(
  registry: LayoutRegistry,
  diagram: DiagramModel,
  name: string,
  options: UnifiedLayoutOptions = {}
): Promise<UnifiedLayoutResult>

separateOverlappingNodes

THE OVERLAP PASS — one rule, one place, for every path that produces positions.

It lives outside the five algorithms for the same reason packing does: force and community lay out DIMENSIONLESS POINTS and happily return boxes that intersect (see overlap-removal.ts). For every layout that does not overlap — dagre, ELK, tree, grid, circular, radial — it is a no-op, so it costs them one comparison pass and nothing else.

WHY IT IS EXPORTED, which is the bug.

It used to be a closure inside layoutWithComponentPacking, reachable only from adapter.apply(). But the layout HOST — the path engine.layout() actually takes — does not call apply() for a steppable algorithm: it drives createRun()/step()/snapshot() so the run can report progress and be cancelled. snapshot() was returned RAW.

Force is the only steppable built-in. So the one algorithm that genuinely needs overlap removal was the one algorithm that never got it, and engine.layout('force') handed back overlapping node boxes — while every unit test stayed green, because they all go through apply().

A demo caught it in the first thirty seconds of being pointed at a real browser.

ts
Copy
function separateOverlappingNodes(
  nodes: readonly NodeModel[],
  positions: Map<string, { x: number; y: number }>,
  options: UnifiedLayoutOptions = {}
): Map<string, { x: number; y: number }>