Skip to content

layout-algorithm-specification.md

Latest commit

 

History

History
811 lines (562 loc) · 52.5 KB

layout-algorithm-specification.md

File metadata and controls

811 lines (562 loc) · 52.5 KB
Raw

Space-Time Map Layout Algorithm Specification

Version 0.3.0

Companion to: spacetime-map-specification.md Worked examples: layout-algorithm-worked-examples.md Purpose: Defines how rendering coordinates are computed from IES ontology data. The visual spec defines what must be produced; this document defines the computational pipeline.

1. Design Philosophy

Timeband-First Layout

The core problem with a spatial-first (Y-before-X) layout is that it tries to assign fixed band positions without knowing how much horizontal room each transition will need, leading to misaligned transitions and incorrect nesting when the vertical positions are later forced to change.

The timeband-first algorithm inverts this: it partitions time into discrete horizontal sections first, then determines which entities exist and how they relate in each section, and only then assigns vertical (Y) positions and horizontal widths. The result is a DiagramPlan structure that the rendering layer converts to SVG coordinates without needing to re-derive any layout decisions.

Ordering as the Foundation

Before any layout work begins, all temporal ordering information — from explicit entirelyAfter assertions in the RDF data and from adjacent metric ParticularPeriod timestamps — is unified into a single directed acyclic graph (DAG). This DAG is cycle-checked and forms a hard validation gate: if a contradiction is detected (for example, an explicit ordering assertion that conflicts with metric timestamps), the pipeline halts and returns actionable error messages before any layout coordinates are computed.

This ordering-first approach means:

  • Explicit and metric ordering are validated against each other, not treated as independent layers.
  • The entirelyAfter relationship is not an add-on; it is the canonical ordering mechanism, with metric timestamps providing duration annotations on top of it.
  • No layout work is ever wasted on data that is internally inconsistent.

Key Principles

  • Time drives structure. Mereological relationships (what is part of what) change at known temporal breakpoints. Each timeband represents a period of stable mereological structure.
  • Breakpoints mark stable-state boundaries. A breakpoint timestamp marks the exact X position where a new stable arrangement begins or an old one ends.
  • Vertical layout uses a single global pass. Y positions are computed once from the complete structural tree before per-timeband co-location overrides are applied. This prevents spurious transitions caused by per-timeband layout variability.
  • Horizontal widths follow vertical. Transition widths depend on how far entities must travel vertically; straight-section widths depend on padding rules that require stable vertical layout to be known first.
  • All intermediates are named and testable. Each stage produces a concrete data structure. Unit tests SHOULD assert against these structures directly, not against final SVG output.
  • Rendering order is a rendering concern, not a layout concern. This algorithm produces a DiagramPlan that specifies geometry. The rendering layer is responsible for painter's-algorithm Z-ordering.

2. Algorithm Overview

The pipeline has nine stages executed in sequence. Stage 1 has several internal sub-steps; the remaining stages each correspond to a single exported function.

# Stage Key inputs Key output
1 Ordering Graph Construction RDF store, entities BreakpointList (metric + ordinal), OrderingGraph
2 Timeband Decomposition BreakpointList, entities TimebandList
3 Entity State Resolution TimebandList, RDF store EntityStateMap
4 Co-location Resolution EntityStateMap CoLocationGroups
5 Y-Position Assignment CoLocationGroups, EntityStateMap, settings YLayout
6 Transition Group Construction YLayout, BreakpointList, settings TransitionGroupList
7 Horizontal Section Planning TransitionGroupList, YLayout, settings HorizontalPlan
8 Linear Expansion and Final Emission HorizontalPlan, YLayout, TransitionGroupList DiagramPlan
9 Worm Plan Construction DiagramPlan, EntityStateMap, entities DiagramPlan (with wormPlan populated)

3. Intermediate Data Structures

These are the unit-testable boundaries between stages. Only the fields used by downstream stages are listed; implementations MAY add diagnostic fields.

TemporalBreakpoint {
  timestampMs:       number        Milliseconds since epoch, ascending. NaN for ordinal breakpoints.
  periodUri:         string        IRI of the ParticularPeriod, or 'ordinal:start:<entityId>' / 'ordinal:end:<entityId>'
  endingEntityIds:   string[]      entity IRIs whose fusion/installation ENDS at this breakpoint
  startingEntityIds: string[]      entity IRIs whose fusion/installation STARTS at this breakpoint
  isOrdinal?:        boolean       true when timestampMs is NaN — use isNaN(timestampMs) as the discriminant
}

BreakpointList = TemporalBreakpoint[]
OrderingConstraint {
  earlierId:        string      IRI of the entity that is entirely before the later entity
  earlierBoundary:  BoundaryType  which boundary of earlierId was referenced
  laterId:          string      IRI of the entity that is entirely after the earlier entity
  laterBoundary:    BoundaryType  which boundary of laterId was referenced
}

BoundaryType = 'start' | 'end' | 'entity'
  'start'  — constraint referenced an isAStartOf boundary node
  'end'    — constraint referenced an isAFinishOf boundary node
  'entity' — constraint referenced the entity directly (no boundary node)

OrderingConstraints = OrderingConstraint[]
OrderingGraph {
  topoOrder:          string[]          entity IDs in left-to-right topological order
  boundaryEventOrder: string[]          boundary-event node IDs in topological order; each entry is 'entityId#start' or 'entityId#end'
  constraintPairs:    Set<string>       'earlierId→laterId' strings for O(1) membership lookup (used by Stage 9 for topological boundary inference per §15.11)
  ordinalEntityIds:    string[]          entity IRIs whose start or end is covered only by ordinal breakpoints (not metric ones); used by Stage 3 activation logic
  cycleErrors:        OrderingConstraint[]  constraints that were part of a detected cycle; empty when data is consistent
}
CycleErrorCategory = 'pure-explicit' | 'metric-contradiction'
  'pure-explicit'        — all constraints in the cycle came from explicit entirelyAfter triples; the user has authored conflicting assertions
  'metric-contradiction' — at least one constraint was inferred from metric ParticularPeriod adjacency; an explicit assertion contradicts metric data

CategorisedCycleError {
  category:   CycleErrorCategory
  constraint: OrderingConstraint
  message:    string              human-readable description naming both entities and the source of the conflict
}
Timeband {
  leftBreakpoint:   TemporalBreakpoint | null   null for TB_0 when no entity has a known start
  rightBreakpoint:  TemporalBreakpoint | null   null for TB_last when no entity has a known end
}

TimebandList = Timeband[]
EntityState {
  isActive:                boolean      entity contributes to this timeband
  fusedIntoSlots:          string[]     component slot IRIs this entity is currently installed into
  participatingInFusions:  string[]     Activity / FusionOfIntegralParts IRIs this entity participates in
  participationEntityIds:  string[]     Participation entity IRIs linking this entity to its fusions
  activeSlotFusionIds:     string[]     FusionOfIntegralParts IRIs where this entity is a member slot
  activeStatePartIds:      string[]     temporal-part entity IRIs that are isTemporalPartOf this entity and active in this timeband
  mereologicalParentId:    string | null  direct isPartOf parent IRI (structural, constant across timebands)
}

EntityStateMap = Map<timebandIndex, Map<entityId, EntityState>>

Note: entityId is the map key, not a field of EntityState. entitiesInstalledInSlots is not a direct field; it is derived in Stage 4 from the fusedIntoSlots fields of the entities that are installed into this entity's slots. A per-entity maximum concurrent sub-row count is computed internally by Stage 5 and is not part of this structure.

CoLocationGroup {
  groupId:         string      IRI of the slot-fusion entity, or 'install:<slotId>:<entityId>' for install groups
  memberSlotIds:   string[]    all entity IRIs sharing the same Y band (sorted alphabetically)
  canonicalSlotId: string      anchor for Y assignment (see Stage 4 for selection rule)
}

CoLocationGroups = Map<timebandIndex, CoLocationGroup[]>
YAssignment {
  yStart:  number   top edge in logical units
  height:  number   vertical extent in logical units (constant across all timebands for a given entity)
}

YLayout = Map<timebandIndex, Map<entityId, YAssignment>>
Transition {
  entityId:    string
  fromCenterY: number   center Y of the entity's band in the source timeband (yStart + height/2)
  toCenterY:   number   center Y of the entity's band in the destination timeband (yStart + height/2)
  height:      number   constant band height (guaranteed equal in source and destination timebands)
}

TransitionGroup {
  breakpointIndex:  number          index into BreakpointList identifying the boundary this group straddles
  tickEdge:         'left' | 'right'  which edge of the transition section carries the breakpoint timestamp tick
  transitions:      Transition[]
  widthPx:          number           shared width computed from the maximum center-Y travel in the group
}

TransitionGroupList = TransitionGroup[]

Note: direction ('enter' | 'exit') is computed for each transition during Stage 6 to determine tickEdge but is not stored in the Transition struct. timestampMs is not stored in TransitionGroup; use breakpoints[breakpointIndex].timestampMs when a timestamp is needed.

HorizontalSection {
  sectionType:      'padding-left' | 'straight-A' | 'straight-B' | 'transition' | 'padding-right'
  timebandIndex:    number | null   null for padding sections
  breakpointIndex:  number | null   set only for 'transition' sections
  minWidthPx:       number          hard minimum (the section is never narrower than this)
  desiredWidthPx:   number          width at minimum linear scale (pxPerMsRequired); used for tick placement and pixel↔timestamp conversion; equals minWidthPx for non-bounded sections
  actualWidthPx:    number          final width after Stage 8 expansion (≥ minWidthPx)
}

HorizontalPlan = HorizontalSection[]   ordered left to right
DiagramPlan {
  horizontalPlan:    HorizontalPlan
  yLayout:           YLayout
  transitionGroups:  TransitionGroupList
  canvasWidthPx:     number          the canvas width passed into Stage 8; may be less than totalWidthPx (scroll case)
  totalWidthPx:      number
  totalHeightPx:     number
  minLinearWidthPx:  number | null   minimum canvas width for all bounded timebands to render at proportional widths; null when open-ended timebands exist
  isNonLinear:       boolean         true when any straight-A section is at its minimum width (open-ended, ordinal, or canvas too narrow)
  timeRange:         { startMs: number; endMs: number }
  wormPlan:          WormPlan        populated by Stage 9; empty array until Stage 9 runs
}
WormStyle {
  outlineColor:  string        CSS color for polygon stroke
  outlineWidth:  number        stroke-width in pixels
  outlineDash:   string | null stroke-dasharray value; null = solid line
  fillColor:     string        CSS color for polygon fill
  fillOpacity:   number        0.0–1.0
}

WormSegment {
  xPos:  number   x coordinate of this polygon vertex in diagram-space
  yPos:  number   center Y of the entity at this boundary = YLayout[T_s][E].yStart + height / 2
}
```ts

> **Why boundary-point coordinates?** Each `WormSegment` stores `(xPos, yPos)` — a polygon vertex. The `segments` array contains N+1 entries for N active sections: the first and last entries are the body-face positions (pre-offset for mereological nesting depth), and the inner N−1 entries are the section left-edge boundaries. The renderer traces the polygon by connecting N+1 consecutive dots along the top edge and in reverse along the bottom edge. For transition sections, `yPos[i]` stores the **source Y** at the left boundary; `yPos[i+1]` carries the **destination Y** — so the diagonal emerges naturally as the line connecting two consecutive vertices.

```ts
EntityWorm {
  entityId:      string
  zOrder:        number         non-negative integer; lower = drawn first (background layer)
  unknownStart:  boolean        true → render left face as a leftward-pointing chevron
  unknownEnd:    boolean        true → render right face as a rightward-pointing chevron
  height:        number         entity's constant band height (same value across all timebands)
  segments:      WormSegment[]  N+1 left-to-right vertex points for N active HorizontalPlan sections
  style:         WormStyle
}

WormPlan = EntityWorm[]   sorted ascending by zOrder; rendered sequentially (painter's algorithm)

4. Stage Details

Stage 1 — Ordering Graph Construction

Goal: Build a unified, cycle-checked ordering DAG from all available ordering information (metric timestamps and explicit entirelyAfter assertions), emit a merged breakpoint list that satisfies all ordering constraints, and halt the pipeline early if the data is inconsistent.

Stage 1 has five internal sub-steps executed in sequence.

Sub-step 1.1 — Collect metric breakpoints

Query all ies_top:State instances that have both a bounding predicate (isAFinishOf or isAStartOf, or any sub-property) and isPartOf pointing to an ies_core:ParticularPeriod. Resolve each ParticularPeriod IRI to a millisecond timestamp via ISO 8601 parsing. Group events by resolved timestamp; sort ascending. Populate endingEntityIds and startingEntityIds per breakpoint.

Testable invariants:

  • Breakpoints are strictly ordered by timestampMs (ascending, no duplicates).
  • Every entity with a known temporal bound appears in exactly one metric breakpoint per bound.
  • endingEntityIds and startingEntityIds are mutually exclusive within any one breakpoint.

Sub-step 1.2 — Query explicit ordering constraints

Fetch all ?subject ies_top:entirelyAfter ?object triples. Resolve any subject or object that is a boundary-state node (rather than a diagram entity) to its parent entity via isAStartOf or isAFinishOf. Build directed OrderingConstraint pairs. Deduplicate. Return OrderingConstraints.

Boundary-state resolution rule:

  • X entirelyAfter Y where Y has isAStartOf Z → earlierId = Z (Y is a start-boundary of Z; Z's start precedes X).
  • X entirelyAfter Y where Y has isAFinishOf Z → earlierId = Z (Y is a finish-boundary of Z; Z finishes before X starts).
  • X entirelyAfter Y where Y is itself a diagram entity → earlierId = Y.

Apply the same resolution to X for laterId.

Sub-step 1.3 — Infer metric ordering edges

For each adjacent pair of distinct metric timestamps (T_i, T_j) with T_i < T_j, emit ordering constraints between the entities that bound those breakpoints:

  • For every endingEntityId E at T_i and every startingEntityId F at T_j: emit { earlierId: E, earlierBoundary: 'end', laterId: F, laterBoundary: 'start' }.
  • Emit end → end and start → start adjacency constraints between the two breakpoints to support transitivity through entities whose only known boundary at a timestamp is an end or a start.

These inferred constraints are combined with the explicit constraints from Sub-step 1.2 before the DAG is built. This is what allows contradictions between metric data and explicit assertions to be detected as cycles.

Simultaneous events (same timestamp) generate no inferred edge between them.

Why adjacency-only is sufficient: buildOrderingGraph adds intra-entity entityId#start → entityId#end edges for every entity that appears in the graph. Adjacency between consecutive metric breakpoints plus those internal edges yields the full transitive ordering through Kahn's topological sort. O(N²) all-pairs emission is not required.

Sub-step 1.4 — Build the ordering DAG and detect cycles

Operate at boundary-event level — each entity contributes two nodes: entityId#start and entityId#end. This resolves the entity-level cycle problem that arises when entities overlap (for example, workshop overlaps alice-state-active): at entity level asa→ws and ws→asa appear simultaneously, causing every entity to land in a cycle. At boundary-event level these become ws#start → asa#end (asa ends after ws has already started), which is acyclic.

Mapping a constraint to boundary-event nodes:

earlierBoundary earlier node
'start' entityId#start
'end' entityId#end
'entity' entityId#end (the whole entity ends first)
laterBoundary later node
'start' entityId#start
'end' entityId#end
'entity' entityId#start (the whole entity starts after)

Intra-entity edges entityId#start → entityId#end are added for every entity that appears in the graph (in either a start or end role). Run Kahn's algorithm with alphabetical tie-breaking for determinism. Produce boundaryEventOrder and detect any nodes that remain with non-zero in-degree (cycle participants).

On cycles: collect cycle-participating constraints as cycleErrors. Cycle errors are then classified by Sub-step 1.5. The pipeline MUST halt before Stage 2 if cycleErrors is non-empty.

Sub-step 1.5 — Categorise cycle errors and insert ordinal breakpoints

Cycle categorisation:

Build a key set from the inferred constraint list (Sub-step 1.3) and from the explicit constraint list (Sub-step 1.2). For each constraint in cycleErrors:

  • If the constraint key matches the inferred set and not the explicit set → 'metric-contradiction'. Message: "Metric ParticularPeriod data orders earlierId (earlierBoundary) before laterId (laterBoundary), but explicit entirelyAfter assertions contradict that."
  • Otherwise → 'pure-explicit'. Message: "Explicit entirelyAfter from laterId (laterBoundary) to earlierId (earlierBoundary) conflicts with other assertions in a cycle."

Ordinal breakpoint injection:

For each boundary-event node in boundaryEventOrder that is NOT already covered by a metric breakpoint (i.e., its entity's start or end does not appear in any metric breakpoint's startingEntityIds or endingEntityIds), emit a synthetic ordinal breakpoint:

start node → { timestampMs: NaN, isOrdinal: true, periodUri: 'ordinal:start:<entityId>', startingEntityIds: [entityId], endingEntityIds: [] }
end node   → { timestampMs: NaN, isOrdinal: true, periodUri: 'ordinal:end:<entityId>',   endingEntityIds: [entityId],   startingEntityIds: [] }

Position each ordinal breakpoint relative to the metric breakpoints using topological ordering: insert immediately before the metric breakpoint whose timestamp is the smallest metric timestamp that follows the ordinal node in boundaryEventOrder. Ordinal breakpoints with no following metric anchor are appended after all metric breakpoints.

Entities whose boundaries are covered only by metric breakpoints (not ordinal ones) are still tracked as part of the ordering DAG via ordinalEntityIds — this set drives activation logic in Stage 3.

Testable invariants (Stage 1):

  • cycleErrors.length === 0 for all well-formed data.
  • isNaN(timestampMs) is the sole discriminant for ordinal breakpoints.
  • boundaryEventOrder is a valid topological sort (no node appears before all its predecessors).
  • Metric breakpoints retain their original relative order; ordinal breakpoints are interleaved.

Stage 2 — Timeband Decomposition

Goal: Divide the timeline into the minimal set of horizontal bands covering all stable active periods.

Inputs: BreakpointList (from Stage 1), SpatiotemporalExtent[]

includeFirst = true if any entity has start === undefined (no metric start timestamp — open-started; active from the beginning of the diagram). includeLast = true if any entity has end === undefined (open-ended).

Assemble result in order:

  1. If includeFirst: prepend { leftBreakpoint: null, rightBreakpoint: breakpoints[0] }.
  2. For i = 1…N−1: add { leftBreakpoint: breakpoints[i−1], rightBreakpoint: breakpoints[i] }.
  3. If includeLast: append { leftBreakpoint: breakpoints[N−1], rightBreakpoint: null }.

Assign sequential index values 0…M−1.

Timebands represent the stable intervals between breakpoint ticks only. Rendered transition widths are inserted around those boundaries later (Stages 6–8) but do not change which timestamp bounds a timeband.

Testable invariants:

  • timebandList.length == (breakpoints.length − 1) + (includeFirst ? 1 : 0) + (includeLast ? 1 : 0).
  • Adjacent timebands share exactly one breakpoint.
  • Indexes are sequential from 0.

Stage 3 — Entity State Resolution

Goal: For each timeband, determine which relationships (installations, slot fusions, participations, state parts) are active for each entity.

Activation rule: A fusion, installation, or activity is active in a timeband when:

  • Its start time, if metrically known, is strictly before the timeband's right breakpoint timestamp; and
  • Its end time, if metrically known, is strictly after the timeband's left breakpoint timestamp.
  • An entity with no known metric start is active from Timeband 0 onwards (unless constrained by ordinal activation ranges).
  • An entity with no known metric end remains active through the final timeband.

For ordinal entities (those in ordinalEntityIds from Stage 1): activation is determined by the first and last timebands in which their respective ordinal boundary breakpoints appear, rather than by metric bounds.

Boundary precision: When a start time equals a breakpoint timestamp exactly, the entity is active in the timeband whose left boundary is that breakpoint. When an end time equals a breakpoint timestamp exactly, the entity is active in the timeband whose right boundary is that breakpoint. Both conditions use strict comparisons.

Process:

  1. For each entity, evaluate the activation rule for each timeband.
  2. Populate EntityState.fusedIntoSlots from active Installed entities where this entity is the individual side.
  3. Populate EntityState.activeSlotFusionIds from active FusionOfIntegralParts where this entity is a component slot target AND all other targets of that fusion are also typed as ReplaceableLifespan.
  4. Populate EntityState.participatingInFusions and EntityState.participationEntityIds from Participation entities that are isTemporalPartOf this entity and isPartOf an active fusion. A participation is active in a timeband when its fusion is active (Participation entities carry no temporal bounds of their own).
  5. Populate EntityState.activeStatePartIds from entities that are isTemporalPartOf this entity and active in this timeband, excluding Participation and Installed helper entities.
  6. Populate EntityState.mereologicalParentId from the direct isPartOf relationship (structural; constant across timebands).

Testable invariants (aircraft684 example):

  • TB_0: engine329-installed, sysCompFusion, fuelpump739-installed all active.
  • TB_1: engine329-installed and sysCompFusion inactive; fuelpump739-installed active.
  • TB_2: all three inactive.
  • engine329-fuelpump-component.mereologicalParentId == 'engine329' in all timebands.

Stage 4 — Co-location Resolution

Goal: Identify groups of entities that must share Y coordinates, arising from two sources.

Background: Two reasons entities occupy the same Y band:

  1. Slot-fusion: A FusionOfIntegralParts where all isTemporalPartOf targets are ReplaceableLifespan slots asserts those slots are mereologically the same thing. They MUST share yStart and height.
  2. Installation: An active Installed relationship asserts the installed entity resides within the slot. The entity and its host slot share the same Y band.

Process:

  1. Collect raw groups from both sources:
    • Slot-fusions: For each active slot fusion, create a raw group keyed by the fusion IRI.
    • Installations: For each entity with active fusedIntoSlots, create a raw group keyed by install:<slotId>:<entityId> containing [slotId, entityId].
  2. Merge groups that share any member using Union-Find. Slot-fusion group IDs take precedence over install-derived IDs when merging.
  3. Canonical selection: If exactly one ReplaceableLifespan-typed member exists in the merged group, that slot is canonical. When multiple slots are present (slot-fusion groups), the alphabetically first member IRI is canonical.
  4. Groups with fewer than 2 members are discarded.

Consequence for Stage 5: Installed entities are co-located roots in the Y-position computation, not tree-children of their host slot. The Y co-location constraint is applied in Stage 5 Pass 2.

Testable invariants (aircraft684):

  • TB_0: two groups:
    1. Slot-fusion group (groupId = sysCompFusion): { fuelpump-component, engine329-fuelpump-component, fuelpump739 }, canonical = engine329-fuelpump-component (alphabetically first of the two slot members).
    2. Install group (groupId = install:port-engine-component:engine329): { engine329, port-engine-component }, canonical = port-engine-component (the only ReplaceableLifespan-typed member).
  • TB_1: one group { fuelpump739, engine329-fuelpump-component }.
  • TB_2: no groups.
  • CoLocationGroups.get(timebandIndex).flatMap(g => g.memberSlotIds) has no duplicates per timeband.

Stage 5 — Y-Position Assignment

Goal: Assign yStart and height to every entity for each timeband, satisfying all containment and co-location constraints.

Y positions are computed in two passes. Pass 1 builds a global structural tree and lays out all entities once. Pass 2 applies per-timeband co-location overrides to that single global result.

This single-global-pass design ensures band heights never change between timebands, which is a precondition for Stage 6: if heights were allowed to vary, Stage 6 would generate spurious transitions for height changes rather than genuine mereological moves.

Settings: minBandHeight (default: 30), paddingV (default: 15), rootGap (default: 5), minInternalRowHeight (default: 20).

Pre-computation — sub-row counts

Before Pass 1, compute the maximum concurrent sub-row count for each entity across all timebands: max(participatingInFusions.length + activeStatePartIds.length) over all timebands. This value determines band height and is held constant, so heights never change between timebands.

Pass 1 — Global structural tree layout

Build a global structural tree from mereologicalParentId edges (invariant across timebands). Installed entities are not tree-children of their host slot; they are roots.

Sort roots and children using entityOrder (from LayoutSettings) when provided, falling back to alphabetical-by-entityId for determinism.

Traverse depth-first, leaf-to-root:

  1. Leaf nodes (no structural children): height = max(minBandHeight, subRowCount × minInternalRowHeight). Place at current cursor; advance cursor by height + rootGap.
  2. Internal nodes (with children): advance cursor by paddingV before placing children. After all children are placed:
    • yStart = min(children.yStart) − paddingV
    • height = max(children.yStart + children.height) − yStart + paddingV
    • This yields symmetric paddingV top and bottom around the children block.
  3. Advance the global cursor after each root by root.height + rootGap.

Setting roles: paddingV provides symmetric top/bottom padding inside every container outline. rootGap is the vertical gap between consecutive root-level entities.

Pass 2 — Per-timeband co-location overrides

For each timeband, start from a copy of the globally-computed Pass 1 Y positions. Apply co-location groups in a fixed order: installation groups first, then slot-fusion groups. Processing install groups first ensures that when an installed entity's subtree is repositioned, its structural children move with it before the slot-fusion override runs.

For each group:

  1. Take the canonical member's current Y from the working assignments.
  2. For each non-canonical member, compute delta = canonical.yStart − member.yStart.
  3. Call shiftSubtree(member, delta): shift the member and ALL its structural descendants by delta. This keeps mereological containment intact when an installed entity (which may itself have children) is repositioned.
  4. Pin the member to the canonical's exact yStart and height.
  5. Re-expand the member's structural ancestors bottom-up until the root.

Testable invariants:

  • For any entity A contained in B during timeband T: yStart(A,T) >= yStart(B,T) and yStart(A,T) + height(A,T) <= yStart(B,T) + height(B,T).
  • For any two entities in the same CoLocationGroup in timeband T: yStart(A,T) == yStart(B,T) and height(A,T) == height(B,T).
  • For entities with no mereological relationship and not co-located in timeband T: their Y ranges MUST NOT overlap.
  • height(E,T) is identical in all timebands for any entity E.

Stage 6 — Transition Group Construction

Goal: For each breakpoint, compute the set of entity Y movements (transitions), determine which edge of the transition section carries the breakpoint tick, and compute the shared horizontal width required to render them.

Inputs: YLayout, BreakpointList, EntityStateMap, settings.

Trigger condition: An entity transitions at a breakpoint when its yStart differs between the preceding timeband and the following timeband, AND it is present (active, non-helper) in both. Height is constant across timebands (see Stage 5 pre-computation), so only yStart changes are checked.

Direction rules (applied in priority order):

  1. fusedIntoSlots was non-empty in source and empty in destination → 'exit' (left a slot).
  2. fusedIntoSlots was empty in source and non-empty in destination → 'enter' (entered a slot).
  3. Fallback: toCenterY > fromCenterY → 'exit'; otherwise 'enter'.

Direction is computed to determine tickEdge but is not stored in the Transition struct.

Breakpoint-edge rule:

  • All transitions in the group are 'enter' → tickEdge = 'right'.
  • All transitions are 'exit' → tickEdge = 'left'.
  • Mixed enter/exit at the same breakpoint is not supported in this version; the pipeline MUST surface an error.

Width computation:

verticalTravel(t) = |t.toCenterY − t.fromCenterY|
maxTravel         = max(verticalTravel for all transitions in group)
widthPx           = max(minTransitionWidthPx, maxTravel / transitionRatio)

Settings: minTransitionWidthPx (default: 50 px), transitionRatio (default: 4 vertical units per horizontal pixel).

Testable invariants:

  • All Transition entries in a group share the same breakpointIndex, widthPx, and tickEdge.
  • fromCenterY / toCenterY match YLayout[sourceTimebandIndex][entityId].yStart + height/2 and YLayout[destTimebandIndex][entityId].yStart + height/2.
  • For a pure-enter group: tickEdge == 'right'. For a pure-exit group: tickEdge == 'left'.

Stage 7 — Horizontal Section Planning

Goal: Assign minimum horizontal widths to every section of the diagram.

The diagram's horizontal sections are laid out in this order:

[ padding-left ]
[ straight-A for TB_0 ]
  [ transition at breakpoint 0 ]
  [ optional straight-B after breakpoint 0 ]
[ straight-A for TB_1 ]
  ...
[ straight-A for TB_N ]
[ padding-right ]

Note: there is no straight-B before TB_0.

Padding-left

  1. Find every entity whose start boundary is metrically unknown (entity.start === undefined) and that is active in the first timeband.
  2. For each such entity, determine its nesting depth = number of installation hops and isPartOf ancestor hops to the diagram root.
  3. paddingLeftPx = maxNestingDepth × chevronOffset + minPaddingPx

Straight-A sections

Each timeband produces exactly one straight-A section. minWidthPx = minStraightSectionPx.

Transition sections

A transition section is generated only when a TransitionGroup exists for that breakpoint. minWidthPx = transitionGroup.widthPx. The section's breakpoint tick is placed on transitionGroup.tickEdge.

Straight-B sections

A straight-B section is added immediately after a transition section when at least one entity that just completed a transition at breakpoint Bi also participates in a transition at the immediately following breakpoint B{i+1}.

minWidthPx = paddingBetweenTransitionsPx.

Padding-right

Same calculation as padding-left, but using the entities in the final timeband.

Settings: chevronOffset (default: 20 px), minPaddingPx (default: 20 px), minStraightSectionPx (default: 10 px), paddingBetweenTransitionsPx (default: 20 px).

Testable invariants:

  • Exactly one padding-left and one padding-right section.
  • Exactly timebands.length straight-A sections.
  • Exactly transitionGroups.length transition sections.
  • Number of straight-B sections ≤ number of transition sections.
  • Total section count = 2 + timebandCount + transitionGroupCount + straightBCount.

Stage 8 — Linear Expansion and Final Emission

Goal: Expand straight-A sections proportionally to actual time durations, produce the final DiagramPlan. The HorizontalPlan from Stage 7 defines the minimum-width layout; Stage 8 only adds width, never removes it.

Bounded vs. open-ended timebands: A timeband is bounded when both its leftBreakpoint and rightBreakpoint have known metric timestamps (i.e., neither is null nor ordinal). Only bounded timebands receive proportional metric scaling.

Hard floor:

totalMinWidthPx = sum(section.minWidthPx)
effectiveWidthPx = max(totalMinWidthPx, canvasWidthPx)

Minimum linear width:

pxPerMsRequired = max over bounded timebands of (minStraightSectionPx / tbDurationMs)
minLinearWidthPx = fixedWidthPx + ceil(pxPerMsRequired × totalBoundedDurationMs)

minLinearWidthPx is null when open-ended or ordinal timebands exist (full linearity is impossible).

Desired width per section:

desiredWidthPx = pxPerMsRequired × tbDurationMs   (bounded straight-A)
desiredWidthPx = minWidthPx                        (all other section types, and open-ended/ordinal straight-A)

Expansion:

  1. fixedWidthPx = sum(minWidthPx for all non-bounded-straight-A sections).
  2. availableForBounded = effectiveWidthPx − fixedWidthPx.
  3. For each bounded straight-A section: targetWidthPx = availableForBounded × (tbDurationMs / totalBoundedDurationMs). actualWidthPx = max(targetWidthPx, minWidthPx).
  4. For all other sections: actualWidthPx = minWidthPx.

Mixed diagrams (bounded metric sections AND ordinal sections both present): ordinal sections receive a virtual duration proportional to the average bounded metric section duration scaled by ordinalSectionWidthRatio (default: 0.7). Both compete for the same canvas budget.

isNonLinear: true if ANY straight-A section has actualWidthPx == minWidthPx after expansion (open-ended timebands, ordinal timebands, or canvas too narrow). false only when every bounded section has been meaningfully expanded and no open-ended or ordinal sections exist.

Settings: ordinalSectionWidthRatio (default: 0.7).

Testable invariants:

  • totalWidthPx = sum(sections.actualWidthPx) and totalWidthPx >= totalMinWidthPx.
  • All actualWidthPx >= minWidthPx.
  • For bounded straight-A sections: desiredWidthPx values are proportional to tbDurationMs.
  • If canvasWidthPx >= minLinearWidthPx (non-null) and no ordinal timebands: isNonLinear = false.

Stage 9 — Worm Plan Construction

Goal: Compute a continuous polygon path for every non-helper entity spanning its full temporal extent across all horizontal sections. The worm encodes Y position and height at every section boundary, Z-order, and visual style.

Inputs: DiagramPlan (Stages 1–8), EntityStateMap, SpatiotemporalExtent[], constraintPairs (from Stage 1).

Pass A — Z-order computation

The Z-order is a global constant assigned once and held fixed across all timebands.

  1. Build the structural tree from mereologicalParentId relationships.
  2. Augment with virtual-installed edges: For each entity E that was ever installed into slot S (any timeband), add E as a virtual-installed child of S.
  3. Order children at each node: Structural children first (alphabetically by IRI), then virtual-installed children (alphabetically by IRI).
  4. Depth-first preorder traversal from roots sorted alphabetically. Assign Z-values 0, 1, 2, … as each entity is first visited.

Pass B — Segment construction

Precompute cumulative X offsets: sectionLeftX[i] = sum(actualWidthPx for sections 0…i−1).

For each non-helper entity E, iterate over HorizontalPlan sections left to right, determining the source timeband T_s per section type:

Section type T_s
padding-left First timeband with a YLayout entry for E
straight-A section.timebandIndex
transition (breakpointIndex = B_i) Timeband to the left of B_i
straight-B Destination timeband of the preceding transition
padding-right Last timeband with a YLayout entry for E

Skip sections where E has no YLayout entry for T_s.

For the first segment (i=0, always padding-left):

nestingDepth_start = count of installation hops + isPartOf hops from E to diagram root in T_s
xPos = sectionLeftX[0] + (unknownStart ? nestingDepth_start × chevronSize : 0)
yPos = YLayout[T_s][E].yStart + height / 2

For all subsequent segments (i = 1…N−1):

xPos = sectionLeftX[i]
yPos = YLayout[T_s][E].yStart + height / 2

yPos is always the source timeband's center Y at the left boundary. For transition sections, the destination Y appears automatically in the next segment — connecting consecutive vertices produces the diagonal.

After all active sections, append the terminator segment:

nestingDepth_end = nesting depth of E in its last active timeband
xPos = totalWidthPx − (unknownEnd ? (nestingDepth_end + 1) × chevronSize : 0)
yPos = yPos of the last non-terminator segment

The segments array has exactly N+1 entries for N active sections.

Pass C — Style assignment

Entity classification Condition Style key
Root System isSystem && !mereologicalParentId rootSystem
Structural slot isSystemComponent componentSlot
Installed System isSystem && everHadFusedIntoSlots installedSystem
Installed Artefact !isSystem && !isSystemComponent && everHadFusedIntoSlots installedArtefact
Default band all other non-helper entities defaultBand

everHadFusedIntoSlots is true if EntityState.fusedIntoSlots is non-empty in any timeband.

unknownStart / unknownEnd flags:

Topological inference is mandatory per §15.11 of the visual specification. Boundaries constrained by any ordering edge in constraintPairs — whether from an explicit entirelyAfter triple or inferred from metric adjacency — MUST render as flat vertical edges rather than chevrons.

unknownStart = entity.knownStart ? false : !laterIdSet.has(entityId)
unknownEnd   = entity.knownEnd   ? false : !earlierIdSet.has(entityId)

where laterIdSet and earlierIdSet are derived from constraintPairs.

Settings: chevronSize (default: 10 px).

Testable invariants:

  • Every entity appearing in any YLayout timeband map appears in exactly one EntityWorm.
  • Z-order values are a contiguous range 0…N−1 with no ties.
  • WormPlan is sorted strictly ascending by zOrder.
  • segments has exactly N+1 entries for N active HorizontalPlan sections.
  • segments[0].xPos = nestingDepthStart × chevronSize if unknownStart; sectionLeftX[0] otherwise.
  • segments[N].xPos = totalWidthPx − (nestingDepthEnd+1) × chevronSize if unknownEnd; totalWidthPx otherwise.
  • For inner segments: segments[i].xPos = sectionLeftX[i].
  • For non-transition sections: segments[i].yPos == segments[i+1].yPos (horizontal).
  • For a transition at index i: segments[i+1].yPos = YLayout[T_d][entityId].yStart + height/2.
  • For any mereological parent P containing child C: P.zOrder < C.zOrder.
  • For any entity E ever installed into slot S: S.zOrder < E.zOrder.

5. Global Testable Invariants

These MUST hold on any valid DiagramPlan regardless of input data.

  1. Mereological containment: For any entity A contained in B during timeband T: yStart(A,T) >= yStart(B,T) and yStart(A,T) + height(A,T) <= yStart(B,T) + height(B,T).

  2. Co-location matching: For any two entities in the same CoLocationGroup in timeband T: yStart(A,T) == yStart(B,T) and height(A,T) == height(B,T).

  3. No unrelated overlap: For entities C and D that have no mereological relationship and are not co-located in timeband T: their Y ranges MUST NOT overlap.

  4. Temporal section ordering: All metric breakpoint timestamps are strictly ascending. The left X boundary of any transition section is strictly greater than the left X boundary of all earlier sections.

  5. Transition continuity: For each transition, fromCenterY matches YLayout[sourceTimebandIndex][entityId].yStart + height/2; toCenterY matches YLayout[destTimebandIndex][entityId].yStart + height/2. No horizontal gaps between transition edges and adjacent straight sections.

  6. Breakpoint anchoring: For every TransitionGroup, the rendered breakpoint tick lies on the section edge specified by tickEdge. For a bounded fusion/installation, xStart = tickX(startBreakpoint) and xEnd = tickX(endBreakpoint).

  7. Rigid block consistency: For any System S and sub-entity E that transitions as a rigid block at breakpoint B: both S and E have Transition entries in the same TransitionGroup with identical breakpointIndex, tickEdge, and widthPx.

  8. Padding coverage: paddingLeftPx >= maxNestingDepthUnknownLeft × chevronOffset. paddingRightPx >= maxNestingDepthUnknownRight × chevronOffset.

  9. Section count: horizontalPlan.length == 2 + timebandCount + transitionGroupCount + straightBCount.

  10. Worm Z-order uniqueness: All zOrder values in WormPlan are unique non-negative integers forming a contiguous range 0…N−1.

  11. Worm segment continuity: For any EntityWorm, segments[i+1].xPos == sectionLeftX[i+1] for all inner consecutive pairs (i = 1…N−2). The first and last entries are pre-offset for nesting depth.

  12. Worm segment Y consistency: For non-transition sections: segments[i].yPos == segments[i+1].yPos. For transition sections: segments[i].yPos == YLayout[T_s][entityId].yStart + height/2; segments[i+1].yPos == YLayout[T_d][entityId].yStart + height/2.

  13. Worm structural layering: For any mereological parent–child pair: P.zOrder < C.zOrder. For any installation pair: S.zOrder < E.zOrder.

6. Layout Settings Summary

All settings are logical parameters, independent of any specific implementation technology. Default values are provided; implementations MAY expose these as configurable options.

Setting Default Stage used Description
minBandHeight 30 Stage 5 Minimum height of any rendered band (logical units)
paddingV 15 Stage 5 Symmetric top/bottom padding inside parent containers (logical units)
rootGap 5 Stage 5 Vertical gap between consecutive root-level entities
minInternalRowHeight 20 Stage 5 Height per active participation or state sub-row
entityOrder (absent) Stages 5, 9 Explicit display order: Map<entityId, rank>. Entities absent from the map sort to the end
minTransitionWidthPx 50 Stage 6 Minimum horizontal pixel width for any transition section
transitionRatio 4 Stage 6 Vertical logical-units per horizontal pixel — controls transition slope angle
chevronOffset 20 Stage 7 Horizontal pixel stride per nesting level for padding-left/right width calculation
minPaddingPx 20 Stage 7 Baseline horizontal padding for left/right padding sections
minStraightSectionPx 10 Stages 7, 8 Minimum pixel width for steady-state (straight-A) sections
paddingBetweenTransitionsPx 20 Stage 7 Minimum pixel width for between-transition (straight-B) sections
ordinalSectionWidthRatio 0.7 Stage 8 Virtual duration multiplier for ordinal sections in mixed diagrams
chevronSize 10 Stage 9 Physical tip size in px — baked into segments[0].xPos / segments[N].xPos

7. Future Work

ID Title Description
F-AE-02 Breakpoint merging Merge breakpoints within configurable breakpointMergeThresholdMs of each other. Intended for data where related events are recorded seconds apart but are conceptually simultaneous at diagram scale.
F-AE-03 User-controlled vertical ordering LayoutSettings.entityOrder is partially implemented: the Stage 5 and Stage 9 comparators respect it. The remaining work is a UI affordance (drag to reorder) that writes back the updated order map and triggers a pipeline re-run.
F-AE-04 Non-linear axis indicators When isNonLinear = true, add a visual axis-break marker or annotation to indicate that section widths are not strictly proportional to time. Design needs user testing.
F-AE-05 Deep nesting summarisation Collapsible/expandable system outlines for diagrams with more than 4 nesting levels.
F-AE-06 Entry transitions Currently, only exit transitions are generated when an installation start is unknown (the entity is assumed to have been installed before the diagram's time window). Future work should handle installation starts that are known and occur within the diagram's time window — these generate enter-direction transitions.

Appendix — Relationship to Visual Specification

Visual Spec Rule Algorithm Stage(s)
§4.1.3 — X-axis linear / non-linear Stage 8
§4.2.3 — Vertical nesting encodes mereology Stage 5 (Y assignment, tree internally)
§4.2.5 — Vertical transitions (parallelogram etc.) Stage 6 (geometry); rendering layer (style)
§5.5 — Temporal boundaries (Known / Unknown) Stage 7 (padding calculation), Stage 9 (unknownStart/unknownEnd)
§9.1.1 — Fusion render mode priority Stage 5 (isInstalledSystem rendering hint)
§10.2.1 — SystemElement as dashed band inside System Stage 5 (tree, parent–child)
§10.3 — Installation transitions Stage 6
§10.4 — Co-located slots (fused system components) Stage 4 and Stage 5
§13.8 — Temporal Sequence graph must be acyclic Stage 1 (ordering DAG, cycle gate)
§15.10.4 — Minimise vertical movement Stage 5 (ordering heuristic)
§15.2 — Vertical padding Stage 5 Pass 1, Stage 7
§15.3 — Chevron offset Stage 7 (padding-left / padding-right width)
§15.6 — Transition style Stage 6 (widthPx); rendering layer (visual form)
Worm polygon geometry Stage 9 Pass B (WormSegment vertex points)
Worm Z-order / painter's algorithm layering Stage 9 Pass A (augmented structural + installation tree DFS)
Worm visual styling (outline, fill, opacity) Stage 9 Pass C (WormStyle classification table)
§5.7 — Chevron endpoints for unknown temporal boundaries Stage 9 (unknownStart / unknownEnd flags on EntityWorm)
§15.11 — Topological inference Stage 9 (constraintPairs from Stage 1)