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

# algorithm-minimum-arborescence-tests

The groupant beside algorithms/src/minimum_arborescence/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

- **kind:** groupant
- **status:** partial source derived instance
- **source:** [`algorithms/src/minimum_arborescence/tests.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/minimum_arborescence/tests.rs)
- **source SHA-256:** `64e3192cbca9cd75…`
- **repository folder:** [`algorithms/src/minimum_arborescence/tests.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/minimum_arborescence/tests.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) |
| `oracle` | oracle_relation | partial source derived | [oracle](#oracle) |
| `mutant` | counterfactual_relation | partial source derived | [mutant](#mutant) |
| `coverage` | coverage_relation | partial source derived | [coverage](#coverage) |

## Model text


### descriptant

#### algorithm-minimum-arborescence-tests

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.

Independent cost review falsified the original scan bound. The revised scan stops at every prior traversal; prospective repair and parent source retained in $MOVA_DATA/runs/octopus-wave26-combinatorial-2026-10-30/arbo-repair-prospective.md and arbo-parent.rs.

### model

## algorithm-minimum-arborescence-tests

### Domain

Finite fixture/assertion observations; trusted compiler and test runner; passing is not unrestricted equivalence.

### Forward

4096 directed graph subsets on four vertices, four roots each, mixed signed costs; independent edge-subset reachability/indegree oracle.

### Invariant

Oracle is independently formulated; compare objective/feasibility plus witness invariants, not exact tie witness except named fixtures.

### Cost

O(VE+V^2) time, O(V+E) memory.

### nonbehavior

Type: behavior_complement.

Accepted fixture/output pairs exclude mismatched oracle objectives, invalid witnesses and wrong tested errors. Outside-fixture behavior remains unconstrained.

### preimages

Type: reverse_reconstruction.

A pass reconstructs all implementations agreeing on the finite observations, including faulty unseen extensions. A failed assertion reconstructs unequal compared values at that fixture; it does not uniquely identify a source bug.

### oracle

Type: oracle_relation.

4096 directed graph subsets on four vertices, four roots each, mixed signed costs; independent edge-subset reachability/indegree oracle.

### mutant

Type: counterfactual_relation.

Compiled production mutant must fail the named contractions_extremes_errors assertion; exact restoration followed by positive rerun.

### coverage

Type: coverage_relation.

Adding fixtures intersects the passing implementation set; profile repeats constrain profile-dependent bugs without proving universal correctness.

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

### Cost repair epoch 2026-10-30

Added completed_traversals_are_not_rewalked: root-reaching chains through 512 vertices assert exactly n-1 primary parent advances. Exhaustive 701 root-fixed parent functions through n=5 compare cycle sets and noncycle labels with independent repeated-vertex walks. Nested contraction family k=2,3,4,8,16,32,64,128 has a necessary root-to-star edge of cost k and a matching zero-edge completion witness; tiny instances also use independent edge-subset oracle. Reverting the visited predicate must fail the named visit-count assertion after compilation.

The initial implementation revisited completed root-reaching chains per start. Independent review exhibited 1065024 primary steps for n257/e383 in the nested family, contradicting the originally declared asymptotic bound. Retain that falsified epoch; the revised source enforces a single stamp per round. Counts are operation observations, not runtime benchmarks.

### evidence

#### Evidence

2026-10-30: 4096 directed graph subsets on four vertices, four roots each, mixed signed costs; independent edge-subset reachability/indegree oracle.

Two debug and two release runs, compiled mutation detected by contractions_extremes_errors, 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.

Repair epoch: five focused tests twice debug/release, identical normalized outcomes; compiled completed-traversal stop-condition mutant failed the visit-count assertion and exact restoration passed. Nested-contraction counted probe compares parent and repaired sources without timing. Refreshed paired syntax and source bindings; strict algorithm all-target Clippy. Repair logs use arbo-* in the same receipt directory.

Counted nested family (k=8,16,32,64,128): parent primary advances 324, 2312, 17424, 135200, 1065024; repaired 100, 392, 1552, 6176, 24640. Both return objective k in every case. These are operation counts, not elapsed time or throughput. The retained parent source and instrumented sources are external receipts.