color_step

std.linalg.color_step · Level L3

One move of a backtracking search for a proper colouring with k colours: give vertex p its next colour; if it runs past k (past 1 for vertex 0, since colours are interchangeable), clear it and step back; if it clashes with an earlier neighbour, try the next colour; otherwise go on to vertex p + 1. The body k_colorable runs.

col(p) ← col(p) + 1; past k: back; clash: stay; else: p + 1

Signature

color_step(p: f64[], col: f64[n], A: f64[n, n], k: f64[]) → f64[], 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 next colour for p; back past k; stay on a clash; else forward in exact rational arithmetic, on all 40 test cases.
All 202 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

—

Called by

k_colorable

sha256:3712eb4f9625e403eae0ffddbede50e117dd044d75f5a3a6afd038f97ce31990

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

Control handle

Symbol: Ω:std.linalg.color_step · Ω:color_step
Pins: sha256:3dcb39a4f0cb0e1e98bb49faf0f5468195b5d837922b0a56b828e7513203d36athis graph alone
Evidence: sha256:143735d9b0279a91d60f3d9504d18d6f1e839649046882361a2b3c272837eba4the 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.