eulerian_trail_exists

std.linalg.eulerian_trail_exists · Level L4

Whether a finite undirected simple graph has an Euler trail (a walk using every edge once) and an Euler circuit (one that ends where it started), as 1 or 0 each. Euler's criterion: every vertex with an edge lies in one component, and 0 or 2 vertices have odd degree (0 for a circuit). Isolated vertices do not matter, and a graph with no edges has the empty circuit.

trail ⇔ connected edges and #odd ∈ {0, 2}; circuit ⇔ … and #odd = 0

Signature

eulerian_trail_exists(A: f64[n, n]) → f64[], 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 degree parities and one component among the vertices with an edge in exact rational arithmetic, on all 40 test cases.
All 80 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

component_labels

Called by

—

sha256:e16f9592e8f7f5df31f102c641816cdc040326dbd9a7da138c944703f6d9a17f

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

Control handle

Symbol: Ω:std.linalg.eulerian_trail_exists · Ω:eulerian_trail_exists
Pins: sha256:e62c35efb87fc6310a83ab2bb2347166790b789a3964f7dcf228490200e50d6fthis graph and the 3 it reaches through calls
Evidence: sha256:8dcc7c96726a40c76a98945590211194ee760e233da2696dfb1d1e0b4f55e790the 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.