---
title: "algorithm-blossom-matching — Mova code model"
description: "Mova code model of algorithms/src/blossom_matching/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/blossom_matching/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/blossom_matching/mod.rs.groupant/>

# algorithm-blossom-matching

The groupant beside algorithms/src/blossom_matching/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/blossom_matching/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/blossom_matching/mod.rs)
- **source SHA-256:** `d035459425d74487…`
- **repository folder:** [`algorithms/src/blossom_matching/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/blossom_matching/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** | source derived | [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) |
| `preimages` | reverse_reconstruction | partial source derived | [preimages](#preimages) |
| `transition` | specialized_relation | partial source derived | [transition](#transition) |
| `order` | specialized_relation | partial source derived | [order](#order) |
| `coordinate` | specialized_relation | partial source derived | [coordinate](#coordinate) |
| `fiber` | specialized_relation | partial source derived | [fiber](#fiber) |
| `errors` | error_partition | partial source derived | [errors](#errors) |

## Model text


### descriptant

#### algorithm-blossom-matching

Original std-only implementation or original independent fixtures. See source citations. Prospective model was saved before implementation in $MOVA_DATA/runs/octopus-wave26-combinatorial-2026-10-30/prospective.md.

Preserve original coordinates, deterministic ties and distinct validation/resource/infeasibility outcomes. Repeated observations constrain this epoch only.

### model

## algorithm-blossom-matching

### Domain

Bounded undirected zero-based graph; symmetric optional mate array; loops ignored and duplicates collapsed.

### Forward

Alternating BFS contracts odd cycles to their common base; augmenting paths flip matched status and increase cardinality by one.

### Invariant

Mate symmetry, original-edge membership and disjointness survive augmentation; contraction preserves existence of augmenting paths.

### Cost

O(V^3+E log E) time, O(V+E) memory.

### nonbehavior

Type: behavior_complement.

Exclude nonsymmetric, self, nonexistent-edge or nonmaximum matchings; exclude endpoint acceptance and wrong first error.

### preimages

Type: reverse_reconstruction.

Compatible graphs contain returned pairs and admit no larger matching; exact preimages additionally reproduce sorted BFS choices. Adding loops or duplicate edges leaves output unchanged, so graph recovery is nonunique.

### transition

Type: specialized_relation.

Blossom lifting preserves augmenting-path existence through contracted odd alternating cycles.

### order

Type: specialized_relation.

Vertex relabeling preserves cardinality, but tie-selected mates need not commute.

### coordinate

Type: specialized_relation.

Adding graph edges cannot decrease optimal cardinality; matching identity may change.

### fiber

Type: specialized_relation.

Loops and duplicate adjacency occurrences disappear before search, defining exact output fibers.

### errors

Type: error_partition.

Public size caps precede input-order validation, then arithmetic/search. Exact cover budget exhaustion is not infeasibility; closure capacity overflow is not infeasibility. Bounded index arithmetic cannot overflow. Checked i128 arborescence arithmetic remains defensive. Allocation failure is process-level, not returned; no callbacks or external writes. Empty cases and deterministic ties follow API docs.

### Limits

Partial syntax, no macro expansion/type resolution or full formal proof. No justified generic numerical surrogate for categorical witnesses/errors; supported 1/2/5/10% profiles remain absent, not fabricated. No timing claims. Allocation failure untested.

### evidence

#### Evidence

2026-10-30: 33,868 simple graphs over zero through six vertices; independent subset recursion chooses unmatched or paired first vertex; validates symmetry and original edges.

Two debug and two release runs, compiled mutation detected by boundaries_and_flower, restored positive rerun, strict all-target Clippy and twice-identical partial syntax. Logs: $MOVA_DATA/runs/octopus-wave26-combinatorial-2026-10-30. No timing measurement. Allocation failures and defensive i128 overflow unexercised.