Subgraphs, traversal, cuts, and drawing

Linnet algorithms operate on a graph together with an explicit subgraph view. This lets one algorithm work on the full graph, a selected region, or the boundary created by cutting paired half-edges. Choose the subgraph representation by operation: bit-backed sets are efficient for repeated set algebra, while borrowed or mapped views avoid copying when identity must remain attached to the owning graph.

Traversal and connectivity

A traversal needs a starting half-edge or node, the active subgraph, and a policy describing which adjacent half-edges may be crossed. Results retain typed indexes into the original graph. Breadth-first traversal is useful for distance layers and connectivity; depth-first traversal is useful for trees, back edges, and decompositions. A traversal tree is a derived view, not a new graph, so mutations must be coordinated with the indexes it contains.

Connectivity and traversal results depend on the chosen subgraph. Run an operation on the full graph only when external half-edges and excluded nodes should participate in the answer. Linnet does not currently expose a dedicated articulation-point or biconnected-component API; derive those from traversal data only when your application owns that algorithm and its tests.

Cycles and cuts

cycle_basis returns an independent cycle vector together with the spanning forest used to construct it. Use cyclotomatic_number when the numerical cycle rank itself is the result. all_cycles expands a basis and can grow exponentially; prefer a basis when assigning loop momenta. Symmetric differences combine cycle bitsets without inventing new graph identities.

Cut enumeration separates required left and right node sets and returns the left region, cut content, and right region. A cut edge is represented through its half-edges, preserving which side owns each endpoint. Validate direction/flow after enumeration when a physical Cutkosky or tensor-network interpretation depends on orientation.

Enumerate separating cuts

This complete example builds a square with a diagonal and asks for every cut separating opposite nodes. It is the smallest graph that makes the distinction between a path and a cut family visible without external data or drawing support.

use linnet::half_edge::{HedgeGraph, builder::HedgeGraphBuilder};

fn main() {
    let mut builder = HedgeGraphBuilder::new();
    let a = builder.add_node(());
    let b = builder.add_node(());
    let c = builder.add_node(());
    let d = builder.add_node(());

    builder.add_edge(a, b, (), true);
    builder.add_edge(b, c, (), true);
    builder.add_edge(c, d, (), true);
    builder.add_edge(d, a, (), true);
    builder.add_edge(b, d, (), true);

    let graph: HedgeGraph<(), (), ()> = builder.build();
    graph.check().expect("the half-edge involution is valid");
    let cuts = graph.all_cuts_from_ids(&[a], &[c]);

    assert_eq!(cuts.len(), 4);
    println!("separating cuts: {}", cuts.len());
}

The expected invariant is four distinct left/cut/right partitions separating a from c. Changing the diagonal changes that count, while changing only node or edge payloads does not. The native HedgeGraph Rustdoc and builder Rustdoc give the exact compiled type boundaries for this revision.

Mutation boundaries

Extraction copies a selected region, excision separates a graph along its boundary, sewing joins compatible dangling half-edges, and contraction identifies structure. These operations return mappings or replacement indexes where needed. Keep those results: a numeric Hedge or NodeIndex from before a storage-changing operation is not automatically a valid index into the resulting graph.

DOT and drawing

DOT parsing and emission are interchange/debugging boundaries. Attributes can carry graph, node, edge, and half-edge data, but the typed Rust invariants are reconstructed by the parser; handle parser errors before running algorithms. The drawing feature enables layout; rendering belongs to a DOT consumer, Clinnet, or Linnest. Layout coordinates are presentation data and may vary without changing topology, subgraph membership, or edge flow.