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

# algorithm-prim

The groupant beside algorithms/src/prim/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 descriptive instance
- **source:** [`algorithms/src/prim/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/prim/mod.rs)
- **source SHA-256:** `222dd71ec5789ca5…`
- **repository folder:** [`algorithms/src/prim/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/prim/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** | partial | [approximant](#approximant) |
| **ast** | partial | `syntax.json` |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | [invariant](#invariant) |
| **tests** | executed bounded checks | [tests](#tests) |

## 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 |
|---|---|---|---|
| `behavior-complement` | behavior_complement | partial source derived model | [behavior-complement](#behavior-complement) |
| `reverse-reconstruction` | reverse_reconstruction | partial source derived model | [reverse-reconstruction](#reverse-reconstruction) |
| `cut-choice` | greedy_optimality | partial source derived model | [cut-choice](#cut-choice) |
| `tie-order` | canonical_trace | partial source derived model | [tie-order](#tie-order) |
| `orientation` | undirected_equivalence | partial source derived model | [orientation](#orientation) |
| `scaling` | positive_weight_equivariance | partial source derived model | [scaling](#scaling) |
| `loop-fiber` | ignored_edge_preimage | partial source derived model | [loop-fiber](#loop-fiber) |
| `validation` | error_and_numeric_boundary | partial source derived model | [validation](#validation) |

## Model text


### descriptant

#### prim mod.rs

Check limits then each edge endpoint in input order, u before v. Ignore validated loops. Visit components from smallest unvisited root. Insert incident edges in a min heap keyed by (weight,min endpoint,max endpoint,index), discard edges with both ends visited, and accept each crossing minimum into the growing tree. Sum weights in checked u128.

Epoch 2026-10-30: original implementation and finite independent witnesses. O(V+E log(E+1)) time and O(V+E) storage. Every edge is inserted at most twice; stale internal edges are charged. Limits precede allocations; allocator failures are not typed.

Composition: Uses existing Kruskal Edge and Forest records; algorithmic optimum is additionally compared with Kruskal. Tie trace need not coincide.

No executable percentage-error surrogate: the public operation remains exact, and no useful approximate observation metric is claimed. Allocation failure, timing and general semantic resolution remain outside these models.

### approximant

#### Forward and cost

Domain: Vertex count and ordered undirected kruskal::Edge records with u64 weights, at most one million vertices and edges. Return kruskal::Forest with original indices in Prim acceptance order.

Check limits then each edge endpoint in input order, u before v. Ignore validated loops. Visit components from smallest unvisited root. Insert incident edges in a min heap keyed by (weight,min endpoint,max endpoint,index), discard edges with both ends visited, and accept each crossing minimum into the growing tree. Sum weights in checked u128.

Cost: O(V+E log(E+1)) time and O(V+E) storage. Every edge is inserted at most twice; stale internal edges are charged. Limits precede allocations; allocator failures are not typed.

### invariant

#### Invariant

Accepted edges cross the visited cut and never create a cycle. Every input connected component is spanned; accepted edge count is V-components. Total weight is minimum among all forests spanning original components. Isolated vertices count as components.

### catalog

## Typed model family

### behavior-complement

Type: behavior_complement. Subject/revision: mod.rs sha256 222dd71ec5789ca54d3665bab9ffcae3f01e0b9c4d35ecf093e96e70c733e6b6.
Domain: Vertex count and ordered undirected kruskal::Edge records with u64 weights, at most one million vertices and edges. Return kruskal::Forest with original indices in Prim acceptance order.
Observation: complete one-call return; tests observe named pass/failure.
Operator: Let U be declared inputs crossed with returned observations and R the forward relation in approximant.md. C=U minus R includes wrong first errors, wrong values and forbidden results. This is an exact specification complement and partial source-derived model, not a measured global Rust complement. Accepted edges cross the visited cut and never create a cycle. Every input connected component is spanned; accepted edge count is V-components. Total weight is minimum among all forests spanning original components. Isolated vertices count as components. 
Approximation: exact specification under stated assumptions; partial source correspondence.
Assumptions: standard Rust integer semantics, trusted compiler and successful allocation; limits and order as documented.
Evidence: 4 tests: 761 weighted simple graphs on 0..4 vertices, each possible edge absent/0/3, compared with independent subset spanning optimum and traversed components; Kruskal weight/component agreement; deterministic ties, parallel edges, loops, isolates, wide sum, limits, orientation and scaling. See tests.md for execution and controls.
Status: partial_source_derived_model. No semantic AST or general proof.

### reverse-reconstruction

Type: reverse_reconstruction. Subject/revision: mod.rs sha256 222dd71ec5789ca54d3665bab9ffcae3f01e0b9c4d35ecf093e96e70c733e6b6.
Domain: Vertex count and ordered undirected kruskal::Edge records with u64 weights, at most one million vertices and edges. Return kruskal::Forest with original indices in Prim acceptance order.
Observation: complete one-call return; tests observe named pass/failure.
Operator: Pre(y)={x in domain | R(x,y)} retains all compatible inputs. Outputs lose redundant edges and intermediate heap/pivot traces; errors retain all graphs sharing their first-failure condition. No unique recovery or inverse executor is claimed.
Approximation: exact specification under stated assumptions; partial source correspondence.
Assumptions: standard Rust integer semantics, trusted compiler and successful allocation; limits and order as documented.
Evidence: 4 tests: 761 weighted simple graphs on 0..4 vertices, each possible edge absent/0/3, compared with independent subset spanning optimum and traversed components; Kruskal weight/component agreement; deterministic ties, parallel edges, loops, isolates, wide sum, limits, orientation and scaling. See tests.md for execution and controls.
Status: partial_source_derived_model. No semantic AST or general proof.

### cut-choice

Type: greedy_optimality. Subject/revision: mod.rs sha256 222dd71ec5789ca54d3665bab9ffcae3f01e0b9c4d35ecf093e96e70c733e6b6.
Domain: Vertex count and ordered undirected kruskal::Edge records with u64 weights, at most one million vertices and edges. Return kruskal::Forest with original indices in Prim acceptance order.
Observation: complete one-call return; tests observe named pass/failure.
Operator: At each nonempty frontier the smallest heap key among crossing edges is safe by the minimum-cut exchange rule. Discarded internal edges cannot connect new vertices. Exhaustive subset optimum verifies finite instances independently.
Approximation: exact specification under stated assumptions; partial source correspondence.
Assumptions: standard Rust integer semantics, trusted compiler and successful allocation; limits and order as documented.
Evidence: 4 tests: 761 weighted simple graphs on 0..4 vertices, each possible edge absent/0/3, compared with independent subset spanning optimum and traversed components; Kruskal weight/component agreement; deterministic ties, parallel edges, loops, isolates, wide sum, limits, orientation and scaling. See tests.md for execution and controls.
Status: partial_source_derived_model. No semantic AST or general proof.

### tie-order

Type: canonical_trace. Subject/revision: mod.rs sha256 222dd71ec5789ca54d3665bab9ffcae3f01e0b9c4d35ecf093e96e70c733e6b6.
Domain: Vertex count and ordered undirected kruskal::Edge records with u64 weights, at most one million vertices and edges. Return kruskal::Forest with original indices in Prim acceptance order.
Observation: complete one-call return; tests observe named pass/failure.
Operator: Fix ordered edge records: roots increase; candidate order is (weight,min endpoint,max endpoint,index). Parallel equal edges prefer the earlier original index when simultaneously eligible. Output order can differ from Kruskal; only optimum weight/components are compared across algorithms.
Approximation: exact specification under stated assumptions; partial source correspondence.
Assumptions: standard Rust integer semantics, trusted compiler and successful allocation; limits and order as documented.
Evidence: 4 tests: 761 weighted simple graphs on 0..4 vertices, each possible edge absent/0/3, compared with independent subset spanning optimum and traversed components; Kruskal weight/component agreement; deterministic ties, parallel edges, loops, isolates, wide sum, limits, orientation and scaling. See tests.md for execution and controls.
Status: partial_source_derived_model. No semantic AST or general proof.

### orientation

Type: undirected_equivalence. Subject/revision: mod.rs sha256 222dd71ec5789ca54d3665bab9ffcae3f01e0b9c4d35ecf093e96e70c733e6b6.
Domain: Vertex count and ordered undirected kruskal::Edge records with u64 weights, at most one million vertices and edges. Return kruskal::Forest with original indices in Prim acceptance order.
Observation: complete one-call return; tests observe named pass/failure.
Operator: Swapping endpoints of valid edges preserves heap keys, adjacency incidence, accepted original indices, total and components. Invalid inputs do not obey this equivalence because u-before-v validation is observable.
Approximation: exact specification under stated assumptions; partial source correspondence.
Assumptions: standard Rust integer semantics, trusted compiler and successful allocation; limits and order as documented.
Evidence: 4 tests: 761 weighted simple graphs on 0..4 vertices, each possible edge absent/0/3, compared with independent subset spanning optimum and traversed components; Kruskal weight/component agreement; deterministic ties, parallel edges, loops, isolates, wide sum, limits, orientation and scaling. See tests.md for execution and controls.
Status: partial_source_derived_model. No semantic AST or general proof.

### scaling

Type: positive_weight_equivariance. Subject/revision: mod.rs sha256 222dd71ec5789ca54d3665bab9ffcae3f01e0b9c4d35ecf093e96e70c733e6b6.
Domain: Vertex count and ordered undirected kruskal::Edge records with u64 weights, at most one million vertices and edges. Return kruskal::Forest with original indices in Prim acceptance order.
Observation: complete one-call return; tests observe named pass/failure.
Operator: Multiply all weights by positive integer k while keeping u64 products representable. Heap comparisons and ties stay identical; accepted indices/components stay fixed and total multiplies by k. Executed k=7.
Approximation: exact specification under stated assumptions; partial source correspondence.
Assumptions: standard Rust integer semantics, trusted compiler and successful allocation; limits and order as documented.
Evidence: 4 tests: 761 weighted simple graphs on 0..4 vertices, each possible edge absent/0/3, compared with independent subset spanning optimum and traversed components; Kruskal weight/component agreement; deterministic ties, parallel edges, loops, isolates, wide sum, limits, orientation and scaling. See tests.md for execution and controls.
Status: partial_source_derived_model. No semantic AST or general proof.

### loop-fiber

Type: ignored_edge_preimage. Subject/revision: mod.rs sha256 222dd71ec5789ca54d3665bab9ffcae3f01e0b9c4d35ecf093e96e70c733e6b6.
Domain: Vertex count and ordered undirected kruskal::Edge records with u64 weights, at most one million vertices and edges. Return kruskal::Forest with original indices in Prim acceptance order.
Observation: complete one-call return; tests observe named pass/failure.
Operator: Adding valid self-loops preserves output indices of earlier edges, total and components within limits. A forest observation cannot recover ignored loops, discarded cycle edges or their weights. Executed redundant-loop fixture.
Approximation: exact specification under stated assumptions; partial source correspondence.
Assumptions: standard Rust integer semantics, trusted compiler and successful allocation; limits and order as documented.
Evidence: 4 tests: 761 weighted simple graphs on 0..4 vertices, each possible edge absent/0/3, compared with independent subset spanning optimum and traversed components; Kruskal weight/component agreement; deterministic ties, parallel edges, loops, isolates, wide sum, limits, orientation and scaling. See tests.md for execution and controls.
Status: partial_source_derived_model. No semantic AST or general proof.

### validation

Type: error_and_numeric_boundary. Subject/revision: mod.rs sha256 222dd71ec5789ca54d3665bab9ffcae3f01e0b9c4d35ecf093e96e70c733e6b6.
Domain: Vertex count and ordered undirected kruskal::Edge records with u64 weights, at most one million vertices and edges. Return kruskal::Forest with original indices in Prim acceptance order.
Observation: complete one-call return; tests observe named pass/failure.
Operator: Vertex/edge caps precede endpoint checks. InvalidEndpoint selects first input edge then u before v. u128 checked sum accommodates paths exceeding u64::MAX; wide two-edge fixture verifies this. TotalWeightOverflow is a defensive branch not reached under caps.
Approximation: exact specification under stated assumptions; partial source correspondence.
Assumptions: standard Rust integer semantics, trusted compiler and successful allocation; limits and order as documented.
Evidence: 4 tests: 761 weighted simple graphs on 0..4 vertices, each possible edge absent/0/3, compared with independent subset spanning optimum and traversed components; Kruskal weight/component agreement; deterministic ties, parallel edges, loops, isolates, wide sum, limits, orientation and scaling. See tests.md for execution and controls.
Status: partial_source_derived_model. No semantic AST or general proof.

### tests

#### Finite evidence

4 tests: 761 weighted simple graphs on 0..4 vertices, each possible edge absent/0/3, compared with independent subset spanning optimum and traversed components; Kruskal weight/component agreement; deterministic ties, parallel edges, loops, isolates, wide sum, limits, orientation and scaling.

2026-10-30: 310 unit tests pass twice debug and twice release, with identical normalized names/results (sha256 3f3c86b69fdc0e79e1f9d3e885301a424073b04198a1874f587647a2a6d07a4e). This file contributes four tests. Six compiled controls (one implementation and one test oracle per algorithm) fail named assertions; restored 310-test suite passes. Algorithm all-target strict Clippy and narrow rustfmt pass. Raw logs are external; no performance gain is claimed.

This source control log sha256: 4b75b712ed0b053c0d2b1d8f722f3a73b68a8ba90e0a31fe5780fb71d961292b. Mutant increments components by two; exhaustive_forests fails.