component_labels

std.linalg.component_labels · Level L2

The connected components of a finite undirected graph (a symmetric 0/1 adjacency matrix): each vertex is labelled by the smallest vertex it can reach, so two vertices share a label exactly when a path joins them. An isolated vertex is a component of its own.

label(i) = min{j : i ⇝ j}

Signature

component_labels(A: f64[n, n]) → f64[n]

Structure

The function as NOVA stores it: one box per input, operation and output, and arrows that carry values. A double border marks another library function this one runs — called once, or by Scan once per element; select it to open that function.

input
operation
constant
call
output

Verification

Signature proven by NOVA’s shape solver, for every size.
Equal to the reference the smallest vertex found by breadth-first search in exact rational arithmetic, on all 40 test cases.
All 168 float64 results are exact: the error is zero.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them exact, with zero error.

Accuracy in detail

correctly rounded (the float64 nearest the exact value): 100%
bit-equal to the NumPy formula in float64: 100%
largest error, in units in the last place: 0

Identity

Calls

reachability

Called by

component_count eulerian_trail_exists tutte_step

sha256:f73fbd40c8e2cddf428770fc0e6f0743b4ffc7aa7a4c130f25510c4b2b6bbe75

The semantic hash of the graph. It changes when the program changes, and never when only its documentation does.

Control handle

Symbol: Ω:std.linalg.component_labels · Ω:component_labels
Pins: sha256:6d26a6258c57d87ec57a0174d586d89df17275a0f095d3159acb4afcec6fa690this graph and the 2 it reaches through calls
Evidence: sha256:29fa3a56f15ed71136d88b3c5c881ba44eb08654b5146a107af91b52d4297407the hash of its verification record
Needs: no capability: a pure function

Through NOVA’s control layer, the symbol launches this function only while the program still matches what it pins: a change to this graph, or to any graph it reaches, needs a migration first.