---
title: "algorithm-maximum-cardinality-search — Mova code model"
description: "Mova code model of algorithms/src/maximum_cardinality_search/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/maximum_cardinality_search/mod.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/maximum_cardinality_search/mod.rs.groupant/>

# algorithm-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

- **kind:** groupant
- **status:** partial source derived instance
- **source:** [`algorithms/src/maximum_cardinality_search/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/maximum_cardinality_search/mod.rs)
- **source SHA-256:** `d6910cc7bbbc8526…`
- **repository folder:** [`algorithms/src/maximum_cardinality_search/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/maximum_cardinality_search/mod.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **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](#forward) |
| **ast** | partial | `syntax.json` |
| **cost** | symbolic unmeasured | [Cost](#cost) |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | source derived | [Invariant](#invariant) |
| **tests** | bounded executed | [evidence](#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](#nonbehavior) |
| `compatible_inputs` | reverse_reconstruction | partial source derived | [compatible_inputs](#compatible-inputs) |
| `prefix_certificate` | greedy_certificate | partial source derived | [prefix_certificate](#prefix-certificate) |
| `row_permutation` | representation_invariance | partial source derived | [row_permutation](#row-permutation) |
| `complete_fiber` | constructive_preimage | partial source derived | [complete_fiber](#complete-fiber) |
| `isolated_extension` | extension_relation | partial source derived | [isolated_extension](#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.