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

# algorithm-eulerian-trail

The groupant beside algorithms/src/eulerian_trail/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/eulerian_trail/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/eulerian_trail/mod.rs)
- **source SHA-256:** `abbe71d3cf6a6945…`
- **repository folder:** [`algorithms/src/eulerian_trail/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/eulerian_trail/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) |
| `orientation` | undirected_representation_equivalence | partial source derived model | [orientation](#orientation) |
| `isolated-extension` | isolated_vertex_extension | partial source derived model | [isolated-extension](#isolated-extension) |
| `identity-permutation` | identity_transport | partial source derived model | [identity-permutation](#identity-permutation) |
| `existence-fiber` | degree_connectivity_precondition | partial source derived model | [existence-fiber](#existence-fiber) |
| `trail-preimage` | edge_incidence_reconstruction | partial source derived model | [trail-preimage](#trail-preimage) |
| `iterative-resource` | cursor_resource_relation | partial source derived model | [iterative-resource](#iterative-resource) |

## Model text


### descriptant

#### eulerian_trail mod.rs groupant

Original Mova Rust code and fixtures; no copied problem-site implementations. Conceptual provenance: standard undirected DFS lowlink separator criteria (Tarjan, Depth-First Search and Linear Graph Algorithms, 1972) and Hierholzer edge-splicing traversal (1873), independently expressed using explicit stacks. Repository search found weighted Kruskal Edge, BFS and SCC but no reusable undirected separator or Euler implementation. The modules reuse bridges::adjacency and its endpoint Error contract; tests reuse independent graph fixtures/closure in bridges::tests.

##### Mathematical combiner

Combine source-bound partial syntax, forward relation, the ordered typed obernant family, invariant, cost and checks by intersecting their constraints. The sibling test groupant observes the exact public function; sibling graph consumers inherit adjacency validation and edge identity. Correct traversal in isolation cannot prove shared dependency wiring or parent library exports. Parent integration is a separate check. Syntax excludes macro expansion and semantic resolution.

##### Modeling epoch 2026-10-30

Prospective expectation: linear production cost, deterministic outcomes, deletion/trail-oracle agreement and compiled mutation rejection. 2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness. Replace if trail.edges.len() != edges.len() with if false; eulerian_trail::tests::exhaustive_trail_oracle rejects the compiled mutant. Initial source formatting and a test-module visibility adjustment preceded the first successful build; no algorithmic fix was needed after oracle execution.

##### Retained limits

O(V+E) time and O(V+E) auxiliary space. Each adjacency entry is consumed at most once; output scan/reversal is linear. No call-stack recursion. Validating endpoints costs O(E) before allocating V adjacency lists. Allocation failure is outside the model. Endpoint orientation preserves valid inputs only; invalid u-before-v precedence is observable. Euler canonical paths need not survive arbitrary edge permutation. Tests are finite and do not prove unbounded correctness. Executable approximation profiles are an explicit gap: separator identity and Euler feasibility are categorical contracts without a defined useful relaxed metric; exact oracle harnesses are not speed surrogates.

### approximant

#### Forward approximant

Use bridges::adjacency for complete endpoint validation before existence decisions. Empty edges return Some(Trail([],[])) if V=0 and Some(Trail([0],[])) otherwise. For nonempty edges require zero or two odd-degree vertices. Start at the smallest odd vertex, otherwise the smallest incident vertex. Iterative Hierholzer scans adjacency in input edge order, marks each edge identity once, and collects vertices and incoming edges on stack exit; reverse both. Return None if collected edge count differs from E, thereby excluding disconnected edge support.

##### Cost

O(V+E) time and O(V+E) auxiliary space. Each adjacency entry is consumed at most once; output scan/reversal is linear. No call-stack recursion. Validating endpoints costs O(E) before allocating V adjacency lists. Allocation failure is outside the model.

Domain: Finite ordered undirected multigraph Edge {u: usize, v: usize} inputs and vertex count V; successful allocations and representable materialized vectors.

All endpoint checks precede traversal. Source correspondence remains partial.

### invariant

#### Invariant

Each used identity enters the explicit stack exactly once; loops have two adjacency entries but one identity. Exit order and incoming edge labels reconstruct a contiguous trail after reversal. Successful output has E unique IDs and E+1 valid vertices for nonempty input; disconnected support fails the final count.

Borrowed inputs remain immutable; outputs and failures are deterministic for fixed ordered inputs.

### catalog

## Typed obernant family

### behavior-complement

Type: behavior_complement. Subject/revision: algorithms/src/eulerian_trail/mod.rs, sha256 abbe71d3cf6a69454b00e5a2dcb59b90946216e53ea5c5fb3887062dcaf7891d.
Domain: Finite ordered undirected multigraph Edge {u: usize, v: usize} inputs and vertex count V; successful allocations and representable materialized vectors.
Observation scope: one completed invocation; allocator failure, timing and external effects excluded.
Operator/target: Let U be declared inputs crossed with all returned Result values, and R the forward specification relation. C=U minus R includes wrong separator memberships, malformed/noncanonical trails, wrong existence decisions and incorrect first-error details. This is an exact specification complement, with only partial source-derived correspondence to actual Rust; no complement guarantee follows merely from a forward approximation.
Approximation semantics: exact specification relation under stated assumptions; partial source-derived correspondence, not an unrestricted proof.
Assumptions: trusted Rust compiler and standard library, successful allocation, fixed ordered inputs, test runner executes every selected assertion.
Evidence: 2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness. Specialized unexecuted generalizations remain mathematical reasoning.
Status: partial_source_derived_model.

### reverse-reconstruction

Type: reverse_reconstruction. Subject/revision: algorithms/src/eulerian_trail/mod.rs, sha256 abbe71d3cf6a69454b00e5a2dcb59b90946216e53ea5c5fb3887062dcaf7891d.
Domain: Finite ordered undirected multigraph Edge {u: usize, v: usize} inputs and vertex count V; successful allocations and representable materialized vectors.
Observation scope: one completed invocation; allocator failure, timing and external effects excluded.
Operator/target: For output y retain Pre(y)={G | R(G,y)} with all compatible V, ordered edges and orientation choices. Separator vectors constrain deletion connectivity rather than recover a unique graph. Euler outputs constrain identity-specific incidences and deterministic traversal; None retains all non-Eulerian valid graphs. Error fibers retain all inputs whose first invalid endpoint equals the reported edge, vertex and V.
Approximation semantics: exact specification relation under stated assumptions; partial source-derived correspondence, not an unrestricted proof.
Assumptions: trusted Rust compiler and standard library, successful allocation, fixed ordered inputs, test runner executes every selected assertion.
Evidence: 2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness. Specialized unexecuted generalizations remain mathematical reasoning.
Status: partial_source_derived_model.

### orientation

Type: undirected_representation_equivalence. Subject/revision: algorithms/src/eulerian_trail/mod.rs, sha256 abbe71d3cf6a69454b00e5a2dcb59b90946216e53ea5c5fb3887062dcaf7891d.
Domain: Finite ordered undirected multigraph Edge {u: usize, v: usize} inputs and vertex count V; successful allocations and representable materialized vectors.
Observation scope: one completed invocation; allocator failure, timing and external effects excluded.
Operator/target: Hold valid ordered edge IDs fixed and swap u/v for any edge; undirected adjacency traversal and results are unchanged. Invalid endpoint precedence is excluded from this equivalence. All-edge reversal is executed on the corpus.
Approximation semantics: exact specification relation under stated assumptions; partial source-derived correspondence, not an unrestricted proof.
Assumptions: trusted Rust compiler and standard library, successful allocation, fixed ordered inputs, test runner executes every selected assertion.
Evidence: 2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness. Specialized unexecuted generalizations remain mathematical reasoning.
Status: partial_source_derived_model.

### isolated-extension

Type: isolated_vertex_extension. Subject/revision: algorithms/src/eulerian_trail/mod.rs, sha256 abbe71d3cf6a69454b00e5a2dcb59b90946216e53ea5c5fb3887062dcaf7891d.
Domain: Finite ordered undirected multigraph Edge {u: usize, v: usize} inputs and vertex count V; successful allocations and representable materialized vectors.
Observation scope: one completed invocation; allocator failure, timing and external effects excluded.
Operator/target: Hold nonempty valid edges fixed and append an isolated vertex. Bridge/articulation answers and the canonical Euler trail are unchanged. Empty Euler input has a special V=0 to V=1 vertex-list change, explicitly excluded.
Approximation semantics: exact specification relation under stated assumptions; partial source-derived correspondence, not an unrestricted proof.
Assumptions: trusted Rust compiler and standard library, successful allocation, fixed ordered inputs, test runner executes every selected assertion.
Evidence: 2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness. Specialized unexecuted generalizations remain mathematical reasoning.
Status: partial_source_derived_model.

### identity-permutation

Type: identity_transport. Subject/revision: algorithms/src/eulerian_trail/mod.rs, sha256 abbe71d3cf6a69454b00e5a2dcb59b90946216e53ea5c5fb3887062dcaf7891d.
Domain: Finite ordered undirected multigraph Edge {u: usize, v: usize} inputs and vertex count V; successful allocations and representable materialized vectors.
Observation scope: one completed invocation; allocator failure, timing and external effects excluded.
Operator/target: Hold an undirected graph fixed and permute input edges. Existence is invariant, but the canonical returned path can change with adjacency order; mapping edge IDs alone need not restore the original path. This distinction is modeled, not an assertion of canonical permutation invariance.
Approximation semantics: exact specification relation under stated assumptions; partial source-derived correspondence, not an unrestricted proof.
Assumptions: trusted Rust compiler and standard library, successful allocation, fixed ordered inputs, test runner executes every selected assertion.
Evidence: 2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness. Specialized unexecuted generalizations remain mathematical reasoning.
Status: partial_source_derived_model.

### existence-fiber

Type: degree_connectivity_precondition. Subject/revision: algorithms/src/eulerian_trail/mod.rs, sha256 abbe71d3cf6a69454b00e5a2dcb59b90946216e53ea5c5fb3887062dcaf7891d.
Domain: Finite ordered undirected multigraph Edge {u: usize, v: usize} inputs and vertex count V; successful allocations and representable materialized vectors.
Observation scope: one completed invocation; allocator failure, timing and external effects excluded.
Operator/target: For nonempty valid G, Some is possible iff all incident vertices form one connected component and exactly zero or two degrees are odd, with loops contributing two. The independent oracle enumerates edge trails directly without using this criterion.
Approximation semantics: exact specification relation under stated assumptions; partial source-derived correspondence, not an unrestricted proof.
Assumptions: trusted Rust compiler and standard library, successful allocation, fixed ordered inputs, test runner executes every selected assertion.
Evidence: 2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness. Specialized unexecuted generalizations remain mathematical reasoning.
Status: partial_source_derived_model.

### trail-preimage

Type: edge_incidence_reconstruction. Subject/revision: algorithms/src/eulerian_trail/mod.rs, sha256 abbe71d3cf6a69454b00e5a2dcb59b90946216e53ea5c5fb3887062dcaf7891d.
Domain: Finite ordered undirected multigraph Edge {u: usize, v: usize} inputs and vertex count V; successful allocations and representable materialized vectors.
Observation scope: one completed invocation; allocator failure, timing and external effects excluded.
Operator/target: Fix a successful observed trail (vertices, IDs) and V. Compatible graphs assign each identity the unordered endpoints of the corresponding consecutive vertex pair, allowing either orientation, and must reproduce the declared deterministic start/traversal. For empty trail use the explicit V=0 versus V>0 convention. Orientation ambiguity remains; this is not unique graph reconstruction.
Approximation semantics: exact specification relation under stated assumptions; partial source-derived correspondence, not an unrestricted proof.
Assumptions: trusted Rust compiler and standard library, successful allocation, fixed ordered inputs, test runner executes every selected assertion.
Evidence: 2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness. Specialized unexecuted generalizations remain mathematical reasoning.
Status: partial_source_derived_model.

### iterative-resource

Type: cursor_resource_relation. Subject/revision: algorithms/src/eulerian_trail/mod.rs, sha256 abbe71d3cf6a69454b00e5a2dcb59b90946216e53ea5c5fb3887062dcaf7891d.
Domain: Finite ordered undirected multigraph Edge {u: usize, v: usize} inputs and vertex count V; successful allocations and representable materialized vectors.
Observation scope: one completed invocation; allocator failure, timing and external effects excluded.
Operator/target: Hold V,E fixed and assume successful allocation. Each of 2E adjacency entries advances one cursor at most once; each discovered vertex or used edge adds at most one active frame. Thus explicit storage is O(V+E) and DFS call-stack depth is constant. A 30000-vertex chain tests a finite boundary, not an allocator bound.
Approximation semantics: exact specification relation under stated assumptions; partial source-derived correspondence, not an unrestricted proof.
Assumptions: trusted Rust compiler and standard library, successful allocation, fixed ordered inputs, test runner executes every selected assertion.
Evidence: 2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness. Specialized unexecuted generalizations remain mathematical reasoning.
Status: partial_source_derived_model.

### tests

#### Checks and evidence

2026-10-30: five tests per module; all 229 crate tests passed twice in debug and twice in release with identical normalized test records. Strict Clippy and rustfmt passed. Each module's compiled production mutant failed one exact oracle test with an assertion and exit 101. Exhaustive corpus: 10,790 graphs (all ordered non-oriented edge records of length 0..5 on 0..3 vertices, plus all simple graphs on 4 and 5 vertices). Fixtures cover invalid endpoint precedence, usize::MAX, loops, parallel edges, disconnected support, isolates, empty graphs, and a 30,000-vertex chain. Finite tests do not establish unrestricted correctness.

Negative control: Replace if trail.edges.len() != edges.len() with if false; eulerian_trail::tests::exhaustive_trail_oracle rejects the compiled mutant.

Run cargo test -p mova-algorithms eulerian_trail::tests after parent exports are integrated. This file source hash: abbe71d3cf6a69454b00e5a2dcb59b90946216e53ea5c5fb3887062dcaf7891d. Raw logs, prospective notes, compiled mutants and Rust orchestration are retained in the external run directory. No measured performance gain is claimed.