subgraph module

Use subgraph to construct and inspect opaque zero-copy selections of half-edges. Pass those selections to graph queries, drawing, and layout functions that accept a subgraph argument.

Concepts

Subgraphs

A subgraph is a dictionary containing half-edge membership, a topology signature, subgraph-wide data, and per-half-edge hedge-data. Annotations remain Typst values: content and callbacks are not serialized through Wasm. Independent selections can annotate the same hedge without changing its graph data or each other.

• subgraph.select(g, nodes: (), edges: (), source: (), sink: (), hedges: ()) selects the union of the supplied references. Node and edge references are Typst labels or numeric IDs, supplied in arrays. nodes selects incident hedges, edges selects both available halves, and source / sink selects the named edges’ structural halves, independently of drawing orientation. hedges selects exact numeric hedge IDs. Unknown references and missing requested halves are errors; an isolated node contributes no hedges.
• subgraph.label(g, label) constructs a subgraph from a base62 label.
• subgraph.bits(g, bits) constructs a subgraph from a boolean hedge array.
• subgraph.compass(g, compass) selects half edges with a DOT compass point.
• subgraph.hedges(sg), subgraph.contains(sg, hedge), and subgraph.contains-edge(sg, edge) inspect membership. The last checks whether either half of an edge record is selected.
• subgraph.complement(g, sg) selects all other hedges. It preserves subgraph-wide data, but the newly selected hedges have no annotations.

subgraph.with-data(g, sg, data: value, hedge: updater) returns an annotated selection. data: auto preserves subgraph-wide data and hedge: none preserves hedge annotations. A non-function hedge value replaces every selected hedge’s annotation. A callback receives its original endpoint record plus edge, edge-name, and flow; data holds the existing selection annotation and graph-data holds the graph’s half-edge data. Its return value replaces the annotation, even when it is none. To store a callback as an annotation, return it from the updater rather than passing it as the updater itself. subgraph.hedge-data(sg, h) reads one selected hedge’s annotation.

Graph-aware consumers check a signature of IDs, names, and source/sink incidence, not graph identity or placement. Selections survive layout and drawing/data changes, but incompatible topology or names are rejected. Re-select on a cut view rather than reusing its master’s selections.

Breaking change: raw subgraph bytes are no longer accepted by public APIs. Use the constructors above, or the wrapped results of graph.cycles and graph.forests, and pass the whole object, not its internal bytes field. subgraph.to-label(sg) exports membership only: rebuilding with subgraph.label(g, label) binds it to that graph but does not restore annotations or the old topology signature. Keep the object to preserve Typst sidecar data; a base62 label is not a complete serialization of an annotated selection.

Passing subgraph: sg to draw highlights half-edges, while layout restricts placement or optimization. Neither opens edges; use graph.cut for that.

Directed Cut Views

graph.cut(g, left: left, right: right, boundary: patch) opens one weighted directed cut and leaves g unchanged. The two selections are its drawing sides, not separate cuts or a partition of the vertices. They must be disjoint and contain exactly opposite halves of every selected paired edge in g. Already dangling edges cannot be selected for opening.

Think of the drawing boundaries as L and R, with a positive seam passage from R to L. Selecting an edge’s source on R and sink on L follows that positive direction; swapping them reverses it. This is independent of superficial drawing orientation, including reversed fermion arrows. Side names do not place endpoints automatically: boundary supplies the view’s geometry.

An annotation (winding: n) on either selected half requests a positive integer number of same-direction passages; it defaults to one. If both halves specify winding, they must agree. Each selected edge becomes a source stub, a sink stub, and n - 1 middle segments. Thus winding two produces three segments without separate named seams or a caller-supplied ordering of cut objects. Winding is not a net count of cancelling back-and-forth crossings.

This small example uses the manual’s existing imports. It stores content on the original edge and endpoints, annotates the cut sides, and opens one edge with winding two. The boundary callback places both ordinary free endpoints and the generated middle endpoints using the same record interface:

#let master = graph.build({
  node(<a>, pos: graph.pos(x: 0, y: 0))
  node(<b>, pos: graph.pos(x: 0, y: -2))
  edge(
    <link>,
    source(<a>, caption: [output]),
    sink(<b>, caption: [input]),
    label: [connection],
  )
})
#let left = subgraph.with-data(
  master, subgraph.select(master, sink: (<link>,)),
  data: [left boundary],
  hedge: h => (winding: 2, caption: h.graph-data.caption),
)
#let right = subgraph.with-data(
  master, subgraph.select(master, source: (<link>,)),
  data: [right boundary],
  hedge: h => (caption: h.graph-data.caption),
)
#let view = graph.cut(master, left: left, right: right, boundary: record => {
  let b = record.boundary
  (pos: graph.pos(
    x: if b.side == "left" { -3 } else { 3 },
    y: -2 * b.crossing,
  ))
})
#let view = layout(view, layout-algo: "tree")
#assert(graph.edges(master).len() == 1)
#assert(graph.edges(view).len() == 3)
#assert(graph.edge-data(view, <link.1>).label == [connection])
#assert(graph.boundaries(view).len() == 4)
#draw(view, edge-label: edge => edge.label)

Fragments are named <link.0> through <link.n> in underlying source-to-sink order, irrespective of L/R or drawing arrows. Unnamed edges use the native prefix __linnest_cut_edge_ID; generated name collisions are errors. Prefer explicit edge names when patching a view. Node, edge, and hedge origin refer to the immediate input graph, including on repeated cuts. Edge origins contain the input edge ID and name, plus segment and winding; uncut edges have segment: none and winding: 0. Node and hedge origins are input IDs; newly generated nodes have origin: none.

Physical graph, node, edge, and half-edge Typst data are remapped, including content and callbacks. Middle source hedges inherit the original sink hedge’s data, and middle sink hedges inherit the original source’s data, following the boundary side they continue. The cut resets fragment geometry for re-layout, rather than copying an old midpoint pin to new endpoints. Apply view-specific bends, placement, labels, and crossing-under targets with graph.map; a reference to a split edge needs the appropriate fragment name.

The boundary callback runs only on newly created endpoints, receiving a node or dangling-edge record and returning ordinary graph.map-style placement/data patches. Its record.boundary has output edge and optional node IDs, the original side’s hedge, side ("left" or "right"), zero-based crossing along underlying flow, data from that hedge’s annotation, cut-data from that side’s subgraph-wide data, and the fragment’s origin at creation. For example, the code above preserves each endpoint caption in boundary.data.caption.

On subsequent cuts, boundary.origin and boundary.hedge still refer to the input to the cut that created the endpoint; side, crossing, data, and cut-data are retained. Only boundary.edge and boundary.node remap to current anchors. Inherited boundaries retain their placements and annotations without invoking the callback again.

graph.boundaries(view) returns these descriptors plus current pos, not coordinates cached at cut time. A dangling endpoint uses its edge position and has node: none; a middle endpoint uses its auxiliary node position. Query after layout, or inside draw-after, to group solved endpoints into background boxes with existing CeTZ primitives. Auxiliary boundary nodes are automatically zero-sized and unpainted, including their labels and custom node-drawing callbacks; they remain addressable anchors for incident edges.

#let g = graph.build({
  graph.node(<a>)
  graph.node(<b>)
  graph.edge(graph.source(<a>, compass: "e"), graph.sink(<b>))
})
#let east = subgraph.compass(g, "e")
#let same = subgraph.label(g, subgraph.to-label(east))
#subgraph.hedges(same).len()

#let g = graph.build({
  graph.node(<a>)
  graph.node(<b>)
  graph.edge(graph.source(<a>), graph.sink(<b>))
})
#let first = subgraph.bits(g, (true, false))
#subgraph.contains(first, 0)

#let g = graph.build({
  graph.node(<a>)
  graph.node(<b>)
  graph.edge(graph.source(<a>, compass: "e"), graph.sink(<b>))
})
#subgraph.hedges(subgraph.compass(g, "e")).len()

#let g = graph.build({
  graph.node(<a>)
  graph.node(<b>)
  graph.edge(graph.source(<a>), graph.sink(<b>))
})
#subgraph.to-label(subgraph.bits(g, (true, false)))

#let g = graph.build({
  graph.node(<a>)
  graph.node(<b>)
  graph.edge(graph.source(<a>), graph.sink(<b>))
})
#subgraph.hedges(subgraph.bits(g, (true, false)))

#let g = graph.build({
  graph.node(<a>)
  graph.node(<b>)
  graph.edge(graph.source(<a>), graph.sink(<b>))
})
#subgraph.contains(subgraph.bits(g, (true, false)), 0)

#let g = graph.build({
  graph.node(<a>)
  graph.edge(<D1>, graph.source(<a>))
  graph.edge(<D6>, graph.sink(<a>))
})
#let left = subgraph.select(g, source: (<D1>,), sink: (<D6>,))
#subgraph.hedges(left)