Constrained

:= []

Layouts for graphs that must obey domain rules. The drawing optimizes stress — drawn distances tracking graph-theoretic distances — while satisfying the given rules: minimum separations, alignments, and containment bands over node coordinates, each on one axis.

Every iteration alternates a stress-descent step with a projection of the drawing onto the rules, so the result satisfies the rules while staying as faithful to graph distances as the rules allow. Each axis's rules are projected together in one minimal-movement solve — alignments merge nodes into a single variable, bands and pins bound it, and separations order the variables — so satisfying one rule never disturbs another; pins are re-asserted exactly afterward.

Conflicting rules are not silently resolved: prepare rejects every conflict its feasibility analysis can prove — a separation made impossible by alignment or by other separations, containment bands with an empty intersection, a pin outside a band, or disagreeing pins in one aligned group — and the result's unsatisfied field lists any rule the finished drawing still violates, which is empty whenever the rules are feasible.

layout checks input and produces the drawing in one call. For repeated layouts of unchanged input, call prepare once and pass the result to layout_prepared.

default_input : Input

The empty graph with no constraints. Replace by record update.

default_settings : Settings

Settings that produce a readable drawing in common cases.

default_run : RunArgs

The fixed default seed and no position hints.

prepare : Input, Settings -> [Ok(ConstrainedPrepared), Err(List(Problem))]

Check the input and settings jointly — reporting every independent problem, and rejecting every rule conflict the feasibility analysis can prove — and precompute what repeated runs reuse.

layout_prepared : ConstrainedPrepared, RunArgs -> Result

Lay out previously prepared input. This operation cannot fail; the result's unsatisfied field lists any rule the finished drawing violates, and is empty whenever the rules are feasible.

layout : Input, Settings, RunArgs -> [Ok(Result), Err(List(Problem))]

Check and lay out input in one call: exactly prepare followed by layout_prepared.

Constraint : [
    Separate({ axis : [X, Y], first : U64, second : U64, gap : F64 }),
    Align({ axis : [X, Y], nodes : List(U64) }),
    Inside({ axis : [X, Y], nodes : List(U64), low : F64, high : F64 }),
]

A rule the drawing must obey, over node indices, on one axis.

Separate keeps the second node's coordinate at least gap beyond the first's on the axis (gap may be negative to allow bounded reordering). Align gives all listed nodes the same coordinate on the axis. Inside keeps every listed node's coordinate within [low, high] — absolute coordinates, which anchor the drawing in place of origin normalization.

Input : {
    graph : {
        nodes : List({ width : F64, height : F64 }),
        edges : List({ from : U64, to : U64 }),
    },
    constraints : List(Constraint),
}

Sized nodes, the edges between them, and the rules the drawing must obey. A node is identified by its index in nodes, an edge by its index in edges, and a constraint by its index in constraints; every output list and every reported problem aligns to those orders.

Settings : {
    node_gap : F64,
    max_iterations : U64,
    tolerance : F64,
    pins : List({ node : U64, x : F64, y : F64 }),
}

node_gap sets the per-hop unit distance: the mean over edges of the endpoint diagonals' average plus the gap (the gap alone if edgeless). Iteration stops when the relative stress change of a step drops below tolerance, when the stress itself becomes negligible (a mean squared relative pair error below tolerance), or at max_iterations. Pinned nodes keep exactly the given position; a node pinned twice keeps the last pin in the list.

Problem : [
    InvalidNodeWidth(U64),
    InvalidNodeHeight(U64),
    MissingEdgeStart(U64, U64),
    MissingEdgeEnd(U64, U64),
    InvalidNodeGap,
    InvalidTolerance,
    MissingPin(U64),
    InvalidPin(U64),
    MissingConstraintNode(U64, U64),
    InvalidConstraintGap(U64),
    InvalidConstraintBand(U64),
    UnsatisfiableSeparation(U64),
    ConflictingInside(U64),
    ConflictingPin(U64),
]

Invalid sizes, edge endpoints, spacing, tolerance, pins, or constraints found while checking input. MissingPin and InvalidPin carry the pin's index in the pins list. The constraint problems carry the constraint's index in the constraints list: MissingConstraintNode adds the missing node index, an InvalidConstraintGap is a non-finite separation gap, and an InvalidConstraintBand is a band without finite low <= high.

On otherwise valid input, prepare also reports every rule conflict its feasibility analysis can prove. UnsatisfiableSeparation is a separation no positions can satisfy together with the alignments and the other rules on its axis — a positive gap inside one aligned group, a member of a positive-total cycle of separations, or a separation that empties a variable's band-and-pin interval. ConflictingInside is a band whose intersection with the other bands on its (alignment-merged) nodes is empty. ConflictingPin — indexed into the pins list — is a pin outside its node's band interval, or one of two disagreeing pins inside one aligned group.

RunArgs : { seed : U32, hints : List({ x : F64, y : F64 }) }

Per-run inputs that select a particular solve: the scatter seed, and optional starting positions — index-aligned, one per node — such as a previous result's positions, which makes a re-run cost only its few iterations.

Result : {
    layout : {
        positions : List({ x : F64, y : F64 }),
        bounds : { x : F64, y : F64, width : F64, height : F64 },
        routes : List(Route),
    },
    convergence : { iterations : U64, converged : Bool },
    unsatisfied : List(U64),
}

Geometry plus the convergence record — how many alternation steps ran and whether the stress settled before the iteration cap — plus the honest rule report. prepare rejects every rule conflict its feasibility analysis can prove; unsatisfied lists the indices (into the input's constraints) of any rule the finished drawing still violates beyond a 1e-9 tolerance, checked directly against the returned positions — a separation's gap shortfall, an alignment's coordinate spread, or a coordinate escaping its band. The unified per-axis projection satisfies every rule kind simultaneously, so it is empty whenever the rules are feasible; only a genuinely infeasible conflict the bounded analysis could not prove leaves it populated. Routes are direct boundary-to-boundary connections. When axis-aligned routes suit the domain better, pass layout.positions and the same graph to Route.layout; routing is a separate geometric operation and does not change the constrained placement.