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

# algorithm-minimum-cost-flow

The groupant beside algorithms/src/minimum_cost_flow/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/minimum_cost_flow/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/minimum_cost_flow/mod.rs)
- **source SHA-256:** `a6de6ae849a183b1…`
- **repository folder:** [`algorithms/src/minimum_cost_flow/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/minimum_cost_flow/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) |
| `potential_transport` | potential_reweighting | partial source derived | [potential_transport](#potential-transport) |
| `zero_capacity` | irrelevant_input | partial source derived | [zero_capacity](#zero-capacity) |
| `capacity_certificate` | feasibility_certificate | partial source derived | [capacity_certificate](#capacity-certificate) |
| `limit_monotonicity` | monotone_extension | partial source derived | [limit_monotonicity](#limit-monotonicity) |

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

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

## minimum_cost_flow mod model

### Forward

Successive shortest augmenting paths, Bellman-Ford over residual arcs. Bound n<=64,m<=512,requested<=1024; reject any original positive-capacity negative cycle globally before even zero requested flow. Flow integral and bounded; shortest residual augmentation preserves minimum cost for current value. Maximize value<=requested then minimize signed i128 cost. Input edge order resolves strict relaxation ties. Checked arithmetic. Cost O((limit+1)V(E+V)), storage O(V+E). No speed claim.

### Invariant

Each residual pair sums to original capacity. Internal flow conservation holds. No negative residual cycle; each augmentation attains a shortest residual path and increases integer value.

### Cost

Successive shortest augmenting paths, Bellman-Ford over residual arcs. Bound n<=64,m<=512,requested<=1024; reject any original positive-capacity negative cycle globally before even zero requested flow. Flow integral and bounded; shortest residual augmentation preserves minimum cost for current value. Maximize value<=requested then minimize signed i128 cost. Input edge order resolves strict relaxation ties. Checked arithmetic. Cost O((limit+1)V(E+V)), storage O(V+E). No speed claim.

### 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 Each residual pair sums to original capacity. Internal flow conservation holds. No negative residual cycle; each augmentation attains a shortest residual path and increases integer value. 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. Given (value,cost,edge_flows), antecedents satisfy capacity bounds, conservation, sum f_e*c_e=cost and lexicographic optimality under limit. Different unused capacities/costs yield the same output. InvalidEdge identifies first bad index; NegativeCycle recovers existence, not location.

### potential_transport

Type: potential_reweighting. Costs c'(u,v)=c(u,v)+h(u)-h(v), all fitting i64, preserve cycle sums and optimal flow value; optimal cost changes by value*(h(source)-h(sink)). Chosen witness can differ only among ties.

### zero_capacity

Type: irrelevant_input. Adding a zero-capacity edge cannot change value or cost, though edge_flows gains a zero. Its endpoints must still validate.

### capacity_certificate

Type: feasibility_certificate. For every output, 0<=f_e<=capacity_e; incoming minus outgoing equals value at sink, -value at source and zero elsewhere. Objective is exact sum f_e*c_e.

### limit_monotonicity

Type: monotone_extension. For limits L<=L' within 1024, achieved value cannot decrease. Cost need not increase when costs are negative. Capped value is min(L, maximum feasible flow).

### 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 minimum_cost_flow. 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/minimum_cost_flow-*.txt. No timing or whole-system improvement claim. Source SHA-256: a6de6ae849a183b1b508ebf475e7b1517b27bbf5c38a04dc6dbe1394e6885697.

### prospective

#### Prospective model — 2026-10-30

Successive shortest augmenting paths, Bellman-Ford over residual arcs. Bound n<=64,m<=512,requested<=1024; reject any original positive-capacity negative cycle globally before even zero requested flow. Flow integral and bounded; shortest residual augmentation preserves minimum cost for current value. Maximize value<=requested then minimize signed i128 cost. Input edge order resolves strict relaxation ties. Checked arithmetic. Cost O((limit+1)VE), storage O(V+E). No speed claim.
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.