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

# algorithm-biconnected-components-canonicalization

The groupant beside algorithms/src/biconnected_components/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_fragment
- **status:** partial source bound model
- **source:** [`algorithms/src/biconnected_components/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/biconnected_components/mod.rs)
- **source SHA-256:** `6b1ce98504a60075…`
- **covers:** Given a total block label for every edge, scan edge IDs in increasing order. Assign an output slot at each label's first occurrence. This preserves equivalence, puts each identity once, and orders blocks by minimum identity in O(E) time and space. Missing or out-of-range labels violate the precondition. (bytes 2841–3276)
- **part of:** [algorithm-biconnected-components](https://md.groupants.elamur.ai/free/en/mova/algorithms/src/biconnected_components/mod.rs.groupant/)
- **repository folder:** [`algorithms/src/biconnected_components/mod.rs.groupant/canonicalization.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/biconnected_components/mod.rs.groupant/canonicalization.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 | [Forward](#forward) |
| **ast** | partial | `../syntax.json` |
| **composition** | partial | [Composition](#composition) |
| **descriptant** | present | [Epoch memory](#epoch-memory) |
| **invariant** | partial | [Invariant](#invariant) |
| **tests** | executed bounded checks | `../model.md#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 |
|---|---|---|---|
| `behavior-complement` | behavior_complement | partial source derived model | [behavior-complement](#behavior-complement) |
| `reverse-reconstruction` | reverse_reconstruction | partial source derived model | [reverse-reconstruction](#reverse-reconstruction) |
| `within-order` | monotone_identity | partial source derived model | [within-order](#within-order) |
| `block-order` | first_occurrence | partial source derived model | [block-order](#block-order) |
| `label-renaming` | internal_name_invariance | partial source derived model | [label-renaming](#label-renaming) |
| `totality` | label_precondition | partial source derived model | [totality](#totality) |

## Model text


Source hash and half-open byte scope are in manifest.json. Domain: reachable entry states from the parent function with successful allocation, trusted Rust compiler/library and fixed input. Observation: scoped exit state or early returned error.

### Forward
Input is a total label vector indexed by edge identity, with labels in 0..blocks. Scan identities ascending; allocate a result block on first encounter of a label and append each identity to its mapped position.

### Invariant
positions[label] is unset exactly before the first encountered identity of that class. At every prefix, output partitions that prefix and blocks are ordered by their first identity.

### Cost
O(E+B) time and space including B output vectors; B <= E. No sort or pairwise comparisons.

### behavior-complement
Type: behavior_complement. Within the declared reachable entry states and scoped return/state observations, let R be the forward relation above. Its complement consists of all incompatible outputs or state transitions: violations of the scoped invariant, incorrect early errors or absent transitions required by R. This is a specification complement, not merely a collection of negative fixtures. Input is a total label vector indexed by edge identity, with labels in 0..blocks. Scan identities ascending; allocate a result block on first encounter of a label and append each identity to its mapped position.
Status: partial_source_derived_model. The domain, observation and assumptions above apply. Evidence is inherited from ../evidence.md; scoped generalizations beyond those finite cases remain unproved.

### reverse-reconstruction
Type: reverse_reconstruction. The canonical output determines the equality relation on input labels, but any injective renaming of used labels and any unused allocated label slots is compatible. Original endpoints and traversal order cannot be recovered.
Status: partial_source_derived_model. The domain, observation and assumptions above apply. Evidence is inherited from ../evidence.md; scoped generalizations beyond those finite cases remain unproved.

### within-order
Type: monotone_identity. Appending the current scanned ID makes each block strictly increasing.
Status: partial_source_derived_model. The domain, observation and assumptions above apply. Evidence is inherited from ../evidence.md; scoped generalizations beyond those finite cases remain unproved.

### block-order
Type: first_occurrence. New output blocks are created at their minimum identity; their minima strictly increase.
Status: partial_source_derived_model. The domain, observation and assumptions above apply. Evidence is inherited from ../evidence.md; scoped generalizations beyond those finite cases remain unproved.

### label-renaming
Type: internal_name_invariance. Any bijection on internal labels preserves the exact output.
Status: partial_source_derived_model. The domain, observation and assumptions above apply. Evidence is inherited from ../evidence.md; scoped generalizations beyond those finite cases remain unproved.

### totality
Type: label_precondition. Missing labels or labels outside positions are excluded entry states; the preceding traversal must establish totality.
Status: partial_source_derived_model. The domain, observation and assumptions above apply. Evidence is inherited from ../evidence.md; scoped generalizations beyond those finite cases remain unproved.

### Composition
This fragment relies on its parent's entry preconditions and establishes only the exit conditions stated here. Parent composition wires traversal labels into canonicalization, or global ordering into checked counting. The next stage's preconditions require all preceding invariants, not merely local test success.

### Epoch memory
Prospective predictions and finite outcomes are retained in the parent model. The child scope clarifies interaction obligations; no independent execution or universal proof is claimed.

2026-11-01 review: once traversal supplies a total label vector, equality of labels, rather than their numeric values, determines the output. The public API's fresh-bridge probe in ../evidence.md checks the composition, not arbitrary synthetic label vectors. Permuting input edge identities does not preserve the literal output: the induced identity permutation must be applied before recanonicalizing.

### Limits
Allocation failure excluded. Partial syntax has no semantic resolution or macro expansion. No useful certified approximation metric was established; exact finite checks are not approximate surrogates.