Elamur Groupants⌕
☰

algorithm-biconnected-components-tests

The groupant beside algorithms/src/biconnected_components/tests.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

componentlabelwhere
approximantpartialForward
astpartialsyntax.json
compositionpartialComposition
descriptantpresentEpoch memory
invariantpartialInvariant
testsexecuted bounded checksevidence

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.

idtypelabelwhere
behavior-complementbehavior_complementpartial source derived modelbehavior-complement
reverse-reconstructionreverse_reconstructionpartial source derived modelreverse-reconstruction
oracleindependent_cycle_oraclepartial source derived modeloracle
metamorphicorientation_isolate_transportpartial source derived modelmetamorphic
resourcebounded_depth_witnesspartial source derived modelresource

Model text

model

algorithm-biconnected-components-tests

Domain

Finite fixtures in this test module, a trusted Rust compiler and standard library, and successful allocation; oracle enumerates edge subsets for multigraphs on at most three vertices and simple graphs on five vertices.

Source: algorithms/src/biconnected_components/tests.rs; SHA-256: 6fe9895acb1ed86fb0eb7bf32cb5dea3d2e7276497fcc1e24354e9ec287239c6. Observation is one completed invocation. Models are exact specifications with partial source correspondence, not semantic AST proofs.

Forward

Enumerate connected degree-two edge subsets independently of lowlink, close common-cycle membership transitively, compare canonical partitions. Cover all ordered edge sequences length 0..4 on 0..3 vertices and all simple graphs on five vertices. Also assert orientation/isolate invariance, identity coverage, explicit loop/parallel/cut-vertex fixture, invalid endpoints and a 30000-vertex chain.

Cost

Exponential small-input oracle cost is intentional and bounded by enumerated fixtures; long-chain checks use linear output storage. No performance conclusion follows from these tests.

Invariant

Each enumerated fixture is checked against a separately expressed expected result; all test assertions must execute.

behavior-complement

Type: behavior_complement. For the declared finite harness relation H, its complement consists of false passes, false failures, skipped intended assertions, wrong enumerated corpus or disagreement with the explicit expected results. This specification is not inferred merely from seeing a red control. 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. Given a passing harness result, retain every implementation agreeing on the executed finite inputs; behavior outside that corpus remains unconstrained. Given an assertion failure, retain every candidate and fixture yielding that discrepancy. Neither outcome uniquely reconstructs production code. 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.

oracle

Type: independent_cycle_oracle. Connected degree-two subset enumeration defines common-cycle membership without using production discovery or lowlink state. 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.

metamorphic

Type: orientation_isolate_transport. Reversing all edge orientations and adding one isolate preserves each expected partition. 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.

resource

Type: bounded_depth_witness. A 30000-vertex chain checks heap-backed traversal and singleton block ordering; it is not a general allocation guarantee. 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.

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.

Review observation, 2026-11-01

The oracle uses iterative subset enumeration and transitive closure, not DAG recursion. For each nonempty connected subset S whose incident degrees are two, it adds S × S and takes reflexive transitive closure on edge IDs. A loop contributes degree two at its vertex, so it cannot share such a connected subset with another edge; two parallel non-loop edges do form such a subset. The exact corpus includes ordered multigraph sequences of length at most four for n = 0..3, and simple graphs at n = 5; it does not enumerate all four-vertex graphs. Reversal and adding an isolate are checked together, only on valid inputs. Invalid endpoint order can change the error under reversal. A passing result constrains this finite set of observations, not arbitrary implementations or graphs. The partition relation cannot recover endpoints: a single loop and a single bridge both yield [[0]]. The behavior complement is relative to the harness specification, not a reconstruction of failing source.

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:

Source SHA-256: 6fe9895acb1ed86fb0eb7bf32cb5dea3d2e7276497fcc1e24354e9ec287239c6. Prospective record: ../prospective.md. Syntax projection generated independently twice and compared byte-for-byte.

Independent review, 2026-11-01

The four focused current tests passed. A separate Rust harness using the actual modules checked two parallel edges plus two loops against the explicit partition [[0,1],[2],[3]], rejected the all-singleton candidate, and checked that reversing two invalid endpoints changes the reported first vertex. This is bounded evidence, not an exhaustive proof of the oracle or production algorithm. The earlier domain text incorrectly described a four-vertex DAG recursion; this test oracle is iterative and includes loops, parallel edges and five-vertex simple graphs.

This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/biconnected_components/tests.rs.groupant/