Elamur Groupantsalgorithm-maximum-cardinality-search
The groupant beside algorithms/src/maximum_cardinality_search/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 | bounded checked | Forward |
| ast | partial | syntax.json |
| cost | symbolic unmeasured | Cost |
| descriptant | present | descriptant |
| invariant | source derived | Invariant |
| tests | bounded executed | 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 |
|---|---|---|---|
nonbehavior | behavior_complement | partial source derived | nonbehavior |
compatible_inputs | reverse_reconstruction | partial source derived | compatible_inputs |
prefix_certificate | greedy_certificate | partial source derived | prefix_certificate |
row_permutation | representation_invariance | partial source derived | row_permutation |
complete_fiber | constructive_preimage | partial source derived | complete_fiber |
isolated_extension | extension_relation | partial source derived | isolated_extension |
Model text
Migration: consolidated into model.md, 2026-11-04, operator decision; fresh hash-bound references to the former files were rebound to the sections below.
descriptant
maximum_cardinality_search mod
Original std-only Rust. Prospective model is retained beside implementation. Source citations identify algorithm provenance; no copied implementation. Exact bounded graph semantics are useful independently of any unmeasured optimization. Finite oracle checks and mutant discrimination improve confidence; groupant count alone proves no improvement.
model
maximum_cardinality_search mod model
Forward
Simple undirected graph n<=256,m<=65536. Reject endpoints, loops, duplicates, asymmetry. Select unnumbered vertex with maximal number of selected neighbors, smallest vertex on ties. O(V^2+E) time and O(V^2) validation storage. Original implementation following Tarjan and Yannakakis (1984). No chordality certificate promised.
Invariant
After t selections weights count exactly neighbors in the t-prefix. Output is a permutation; selected vertices are never selected twice.
Cost
Simple undirected graph n<=256,m<=65536. Reject endpoints, loops, duplicates, asymmetry. Select unnumbered vertex with maximal number of selected neighbors, smallest vertex on ties. O(V^2+E) time and O(V^2) validation storage. Original implementation following Tarjan and Yannakakis (1984). No chordality certificate promised.
nonbehavior
Type: behavior_complement. Let R be the deterministic relation specified by Forward including validation precedence and tie rules, X the declared input type and Y its Result type. Behavior complement is (X times Y) minus R. Specifically outputs violating After t selections weights count exactly neighbors in the t-prefix. Output is a permutation; selected vertices are never selected twice. are excluded; a valid-input Err or a wrong successful witness is excluded. Resource, cycle and structural rejections are determined before algorithmic output.
compatible_inputs
Type: reverse_reconstruction. An order p admits every simple undirected graph for which at step t p[t] maximizes prefix-neighbor count with smallest-ID ties. Both empty and complete graphs yield ascending order; graph recovery is nonunique.
prefix_certificate
Type: greedy_certificate. For each prefix P and next v, count(N(v) intersect P)>=count(N(w) intersect P) for every unselected w; equality requires v<=w. These inequalities characterize the complete deterministic order.
row_permutation
Type: representation_invariance. Permuting each adjacency row preserves the successful order because only neighbor membership matters.
complete_fiber
Type: constructive_preimage. Every complete graph K_n and every edgeless graph on n vertices produces [0,...,n-1]. These distinct antecedents demonstrate ambiguity for n>=2.
isolated_extension
Type: extension_relation. Appending one isolated largest-ID vertex leaves the old order as a prefix: its weight is zero and its ID loses every zero-weight tie.
Limits
Partial syntax omits macro expansion and type resolution. No executable approximate profile: categorical graph semantics and feasibility have no justified percentage relaxation here. Integer operations are bounded by caps; flow uses checked i128/u64 arithmetic, with Overflow defensive under current caps. No callbacks. Allocator failure is outside typed status.
evidence
Evidence — 2026-10-30
Eleven tests across five algorithms, including independent exhaustive small-domain characterization. This file belongs to maximum_cardinality_search. Two debug and two optimized runs matched normalized statuses. Strict clippy-driver --test -D warnings passed. A compiled production mutant failed a named assertion; exact bytes restored and positive rerun passed. Raw receipts: $MOVA_DATA/runs/octopus-wave25-graphs-2026-10-30/maximum_cardinality_search-*.txt. No timing or whole-system improvement claim. Source SHA-256: d6910cc7bbbc852669798f09345feb08754f09ca7d9934750f419b7a1d8ccaac.
prospective
Prospective model — 2026-10-30
Simple undirected graph n<=256,m<=65536. Reject endpoints, loops, duplicates, asymmetry. Select unnumbered vertex with maximal number of selected neighbors, smallest vertex on ties. O(V^2+E) time and O(V^2) validation storage. Original implementation following Tarjan and Yannakakis (1984). No chordality certificate promised. Allocation failure is outside typed errors. Resource caps precede vertex/edge validation. No callbacks. Exact categorical output has no justified percentage surrogate; executable approximation profiles unsupported.
This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/maximum_cardinality_search/mod.rs.groupant/