mst_prim

std.linalg.mst_prim · Level L3

The weight of a minimum spanning tree of a complete undirected graph with positive edge weights W, by Prim's algorithm from vertex 0: a Scan of prim_step, n steps. The reference is Kruskal's algorithm with union-find, a route independent of Prim's. On ties the tree may differ, but its weight is the same.

min{Σ_{e ∈ T} w(e) : T a spanning tree}

Signature

mst_prim(W: f64[n, n]) → f64[]

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 Kruskal: sorted edges, union-find in exact rational arithmetic, on all 40 test cases.
All 40 float64 results inside the running error bound; the closest uses 41% of it.
Interpreter and NumPy backend return bit-identical results.
At float32 too: the 40 test cases rounded to float32, and 40 of them inside the running error bound at u = 2⁻²⁴; the closest uses 41% of it.

Accuracy in detail

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

Identity

Calls

prim_step

Called by

—

sha256:26a9f523e80ac549742a03ea17f6a9b6fc2f975412682f2ca78d1db0e79648f3

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

Control handle

Symbol: Ω:std.linalg.mst_prim · Ω:mst_prim
Pins: sha256:dc0517ccb1691a3e239d972a651116e67fd1195996d3a7176f7e177beb2fe1e9this graph and the 1 it reaches through calls
Evidence: sha256:311f8cdde0ca69800f3626cd0b9166e8ad63eae671d03e5eaa0696732cdb8b06the 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.