Elamur Groupantsalgorithm-biconnected-components
The groupant beside algorithms/src/biconnected_components/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.
Facts
Implementation material. A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.
Components
| component | label | where |
|---|---|---|
| approximant | partial | Forward |
| ast | partial | syntax.json |
| composition | partial | Composition |
| descriptant | present | Epoch memory |
| invariant | partial | Invariant |
| tests | executed bounded checks | evidence |
Obernants
The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.
| id | type | label | where |
|---|---|---|---|
behavior-complement | behavior_complement | partial source derived model | behavior-complement |
reverse-reconstruction | reverse_reconstruction | partial source derived model | reverse-reconstruction |
orientation | undirected_representation_equivalence | partial source derived model | orientation |
parallel | cycle_membership | partial source derived model | parallel |
loops | loop_convention | partial source derived model | loops |
isolates | isolated_extension | partial source derived model | isolates |
canonical | identity_transport | partial source derived model | canonical |
Parts
Model text
model
algorithm-biconnected-components
Domain
Finite materialized ordered graphs and machine-sized indices, fixed input, successful allocation. Observations are returned Result values; allocator failure and wall-clock timing are outside the relation.
Source: algorithms/src/biconnected_components/mod.rs; SHA-256: 6b1ce98504a60075c4d2d5eefba280a9efecb295eed946c1a4a7628578e09f45. Observation is one completed invocation. Models are exact specifications with partial source correspondence, not semantic AST proofs.
Forward
Validate endpoints in edge order, u before v, through bridges::adjacency. Partition non-loop edge identities by the equivalence relation generated by membership in a common simple cycle; parallel edges form a two-edge cycle. Each loop and each bridge is a singleton. Isolates produce nothing. Return sorted IDs in blocks ordered by minimum ID.
Cost
O(V+E) time and auxiliary space, including adjacency, vertex state, edge stack, labels and output. Each adjacency entry is consumed once, each non-loop identity pushed and popped once, and canonicalization scans identities once without sorting. Validation is O(E) before V adjacency allocation. All counts/indexes fit materialized vectors. Explicit stacks avoid recursive DFS.
Invariant
Discovery numbers are unique. low[v] is the minimum discovery reachable by descending the active DFS subtree and at most one ancestor back edge. The pending edge stack contains precisely discovered non-loop edges not assigned to a completed block. Parent exclusion uses identity, not endpoint, preserving parallel edges. Every input edge receives one label. The final scan transports labels into consecutive block indices in first-ID order.
behavior-complement
Type: behavior_complement. For domain D and Result space Y let R be the stated exact forward relation. The behavior complement is (D x Y) minus R, including wrong memberships/counts, malformed canonical outputs, wrong errors and wrong precedence. This is a specification complement; correspondence to source is partial and is not a proof. Domain and observation scope are those above; assumptions are fixed inputs, successful allocation and trusted compiler/library. Evidence: evidence.md. Status: partial_source_derived_model.
reverse-reconstruction
Type: reverse_reconstruction. For partition P, retain all vertex counts and ordered endpoint assignments whose cycle-equivalence classes, singleton loops and bridges equal P. A singleton does not distinguish a loop from a bridge, and no endpoint is uniquely recoverable. Error fibers fix only the first invalid endpoint and preceding valid endpoints. Domain and observation scope are those above; assumptions are fixed inputs, successful allocation and trusted compiler/library. Evidence: evidence.md. Status: partial_source_derived_model.
orientation
Type: undirected_representation_equivalence. Swapping valid edge endpoint orientations preserves every edge class; invalid endpoint order is deliberately excluded. Domain and observation scope are those above; assumptions are fixed inputs, successful allocation and trusted compiler/library. Evidence: evidence.md. Status: partial_source_derived_model.
parallel
Type: cycle_membership. Two parallel non-loop identities share a two-edge cycle and therefore a block. Ignoring all edges to the parent vertex would violate this fiber. Domain and observation scope are those above; assumptions are fixed inputs, successful allocation and trusted compiler/library. Evidence: evidence.md. Status: partial_source_derived_model.
loops
Type: loop_convention. Each self-loop remains its own singleton even at a cut vertex or when several loops share a vertex; the explicit loop convention resolves competing block definitions. Domain and observation scope are those above; assumptions are fixed inputs, successful allocation and trusted compiler/library. Evidence: evidence.md. Status: partial_source_derived_model.
isolates
Type: isolated_extension. Appending isolated vertices leaves the partition unchanged; empty graphs of any vertex count have zero blocks. Domain and observation scope are those above; assumptions are fixed inputs, successful allocation and trusted compiler/library. Evidence: evidence.md. Status: partial_source_derived_model.
canonical
Type: identity_transport. An edge permutation transports equivalence classes by the identity bijection, followed by sorting IDs and blocks. First-encounter canonicalization implements this without comparison sorting. Domain and observation scope are those above; assumptions are fixed inputs, successful allocation and trusted compiler/library. Evidence: evidence.md. Status: partial_source_derived_model.
Composition
Intersect the source projection, forward relation, ordered typed obernants, invariants and finite evidence. Tests constrain observations but do not prove all wiring. Parent library exports and registry integration are checked separately.
For valid G with m edges and an appended edge from an existing vertex to a fresh vertex, the expected public observation is P(G + bridge) = P(G) ++ [[m]]. Traversal must label that bridge separately, and canonicalization must retain prior classes in minimum-ID order. A parallel edge is not such an extension: it can join a former bridge's class. This relation is source-derived and finitely checked, not a universal source proof. Exact traversal labels carry more information than the partition and are not reconstructed by partition equality alone.
Epoch memory
Prospective predictions were saved before implementation in ../prospective.md. Original code and fixtures; conceptual origin: Tarjan (1972) lowlink blocks and Kahn (1962) topological ordering with standard DAG recurrence. Existing bridges adjacency and topological_sort were inspected and reused. Production checks matched the first implementation; no semantic repair was needed.
Limits
Allocation failure is excluded. Syntax projection has no macro expansion or semantic resolution. Finite oracles are not unrestricted proofs. An executable approximate surrogate is an explicit gap: no useful certified relaxed metric was established for edge partitions or exact checked counts; the exact oracle is not a speed surrogate.
evidence
Evidence, 2026-10-30
All 456 algorithm library tests passed twice in debug and twice in release; normalized sorted test records were identical. Each new module contributes four tests. Production mutations: replace the lowlink block boundary with true, rejected by articulation_parallel_loops; replace source count one with zero, rejected by exhaustive_path_enumeration. Both compiled and failed named equality assertions; original source bytes were restored and all four tests per module passed again. Strict production Clippy passed. These are finite observations, not speed or unrestricted correctness claims.
External evidence under $MOVA_DATA/runs/octopus-wave18-graphs-2026-10-30:
- debug1.log: SHA-256 52e7cb6f6804a8f61117fa43e11a2d1b38c676bd6ac2c349c0792c962e7ca8a4
- debug2.log: SHA-256 4cadee5560ff9f7b3b08e46b8bb567484fb81467c987b63af10bc3e8f295f611
- release1.log: SHA-256 b4c009e36790c35faed12b982dbfe6ca9497392852475f7d413621ae2cb7ed62
- release2.log: SHA-256 b06e3f678be609b17a452d67f20a6a5c06f863297690f75c1b4987aeb92bd0c5
- biconnected_components-negative.log: SHA-256 981e8729d09a2cd71fdf0e04704473e09fac3612e949cf2fd8011930b103449b
- dag_path_count-negative.log: SHA-256 c1e9876c08d4d9576d9c0f9589629e55d06dce40bd12687247783812d3efa819
- biconnected_components-restored.log: SHA-256 23bf086daee1a998579ff3e5f6bcd888be1920b0ca2f91d541b239065db9751e
- dag_path_count-restored.log: SHA-256 7f5bb86f3fc328658d1ebfe46f01a4ea0a8b2d2c98b4280d063057dafdb883a8
- verification.log: SHA-256 5bb68adc6867078baf71c9847f8e324385ff00a3eedb030cb3f8779b2e4aa555
- clippy.log: SHA-256 279a2a959ef9d6d5796b3d61c052347cef8707316fbe2730f51e2120605785b0
Source SHA-256: 6b1ce98504a60075c4d2d5eefba280a9efecb295eed946c1a4a7628578e09f45. Prospective record: ../prospective.md. Syntax projection generated independently twice and compared byte-for-byte.
Bounded composition review, 2026-11-01
An external Rust probe called the public API on 4,912 ordered multigraph/fresh-bridge extensions (one to three original vertices, at most four original edges, loops and parallel edges allowed). Every result retained the old canonical partition and appended the new singleton. A parallel edge joined its earlier edge instead, and an edge-ID permutation changed the literal output; these reject overbroad versions of the relation. Existing cycle-subset-oracle tests also passed. The probe observes public output, not internal labels, and is finite evidence rather than a proof. Probe source, prospective hypothesis and execution logs are retained in the independent review cycle 31 run directory under $MOVA_DATA/runs. The source-derived exact-label distinction is recorded in traversal's epoch memory. No timing or approximation claim follows.
prospective
Prospective model, 2026-10-30
Finite ordered undirected multigraph; validate endpoints before traversal using bridges::adjacency. Partition non-loop edges by equivalence generated by sharing a simple cycle; parallel edges form a cycle. Loops and bridges each singleton; isolates omitted. Iterative lowlink stack and linear label canonicalization predict O(V+E) time and space. Every edge appears once. Complement includes wrong splits, merges, omissions and errors. Reverse fiber preserves every graph producing these edge classes, not unique endpoints. Allocation failures excluded. No useful relaxed categorical approximant established.
This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/biconnected_components/mod.rs.groupant/