prim_step

std.linalg.prim_step · Level L3

One step of Prim's algorithm: bring in the vertex outside the tree nearest to it, the smallest on a tie, add that distance to the total, and lower every distance to the new vertex's edges. Once every vertex is in, the step changes nothing. The body mst_prim scans.

j = argmin{dist(i) : i ∉ T}; total += dist(j); dist ← min(dist, Wⱼ)

Signature

prim_step(dist: f64[n], intree: f64[n], total: f64[], t: f64[], W: f64[n, n]) → f64[n], f64[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 the nearest vertex outside; add its distance; dist = min(dist, W[j]) in exact rational arithmetic, on all 40 test cases.
All 344 float64 results inside the running error bound; the closest uses 98% 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 90% of it.

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.50

Identity

Calls

—

Called by

mst_prim

sha256:c2944f16265c1dc1bb099653dda3c2562e6c9e2ade2ab7d69240735f4472c19f

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

Control handle

Symbol: Ω:std.linalg.prim_step · Ω:prim_step
Pins: sha256:b1df32d8c718ff3f5ddf50b6111333ed26d0d540f3309084b4948b7c3bcb0707this graph alone
Evidence: sha256:a0f4784b574b62aead1068e66242bf16cdb96b20750bc81c0ad5fae09eb46336the 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.