Unit 3.8 · about 3 h
111 / 324Graph certificates and exhaustive small-graph validation
An algorithm without an independent checker is a rumor. Certificates turn outputs into checkable claims, and generated-graph tests turn examples into evidence.
- implement
- measure
You can now
- Write \(O(V + E)\) checkers for claimed paths, orders and trees that use only the input plus the output.
- Build Hypothesis strategies that generate sparse, dense, disconnected, cyclic and weighted small graphs, and compare against Floyd-Warshall or exhaustive references.
- Measure adjacency representations on matched workloads with timeit, reporting CPU, Python version and setup instead of quoting ratios.
Covers
- Path, ordering and spanning-tree certificates
- Exhaustive small-graph and differential validation
Study, in this order
4 steps
- Hypothesis quickstartHypothesis - generated graph tests
Write your first test (
@givenwith strategies); Dependent generation (@compositeordered_pairs); Combining Hypothesis with pytest - Custom strategies with @compositeHypothesis - generated graph tests
Writing helper functions; Combining
@compositewith parameters; Dependent generation with@composite - Strategies reference: collectionsHypothesis - generated graph tests
Collections (
lists),sampled_fromand composite entries used to build edge lists and weight draws - Floyd-Warshall as the oracleAlgorithms - graph chapters
Section 9.8 (Kleene-Roy-)Floyd-Warshall(-Ingerman): the triple loop over intermediate vertices (printed p. 318)
Focus on
- A certificate is checked by different code than the solver: re-walk parent pointers for distances, scan every edge against a claimed topological order, recount components. \(O(V + E)\) checkers, no shared helpers.
- Generate edge lists with
@composite(draw \(n\), draw \(m\), draw weighted pairs), dedupe parallel edges explicitly, and cover disconnected and cyclic shapes: the default random graph is connected-ish and hides the interesting failures. - Compare on the same instance: Dijkstra against Floyd-Warshall's row, Kruskal against Prim and against brute force at \(n \le 8\). Cross-instance numbers prove nothing.
- Report measurements with setup: BFS on a seeded \(n = 3000\) sparse graph takes about 0.3 ms over the list against about 97 ms over the matrix on 12th Gen i9-12900K with Python 3.13.14. Re-run it; the direction is the claim, not the ratio, and the gap is CPython row-scan overhead, not a portable constant.
Reproduce closed-book
@composite small-graph strategy (\(n \le 7\), derandomize=True) comparing Dijkstra against Floyd-Warshall on nonneg weights passes 100 examples with zero disagreements. Separately, timeit on a seeded \(n = 3000\), 9,000-edge sparse graph shows BFS over the adjacency list at about 0.3 ms against about 97 ms over the matrix. Quote both numbers with CPU and Python version.Traps
- Oracle and solver sharing code: two Dijkstra implementations sharing the
relaxhelper agree even when both are wrong. The oracle must be an independent formulation (triple loop, exhaustive search). - Connected-only generation: strategies drawing \(m \ge n - 1\) edges rarely emit isolated vertices, so component and unreachable handling goes untested. Force sparse and empty draws.
- Quoting the 300x ratio as a constant: it measures CPython-level matrix row scans on one CPU, not an algorithmic invariant. C++ crossover points never transfer without a local measurement.
Practice
LeetCode 417: Pacific Atlantic Water Flow
The \(5 \times 5\) example and the single-cell example
Solve unseen with tags hidden, per the NeetCode pool note: grade the model (which cells are nodes), the assumption (flow direction reversed from borders), the certificate (each claimed cell re-walked downhill to both oceans) and the tests. After-attempt reference is DSA Handbook 8.2 (DFS-from-boundary ladder).
LeetCode 1091: Shortest Path in Binary Matrix
The three listed examples (diagonal path, blocked grid, single cell)
Same unseen discipline: model (8-directional grid graph), assumption (unweighted, so BFS), certificate (re-walked path of the claimed length). After-attempt reference is DSA Handbook 8.1 (LC 1091 ladder entry).
Self-test
-
What makes a checker independent?
It reads only the input and the claimed output, runs a different algorithm than the solver (edge scan, pointer re-walk), and costs \(O(V + E)\). Shared helpers or re-running the solver prove nothing. -
Why is Floyd-Warshall a valid oracle for Dijkstra tests?
It is a three-line triple loop over intermediate vertices with no heap, no settle logic and no stale entries: obviously correct by a separate argument, so agreement isolates Dijkstra's invariant rather than re-testing one implementation twice. Restrict weights to nonneg for the comparison. -
A shrunk Hypothesis failure shows a 3-vertex graph. What do you do?
Keep it as a regression test, read off the violated assumption (disconnected input, parallel edges, self-loop), fix the solver or state the precondition, and re-run the full strategy. -
Why must comparisons share the instance?
Graph shape, density and weight scale all move runtimes and even outputs; different instances confound the comparison. Same seed, same edge list, both algorithms, then compare.
Completion criterion
Stop when
Your differential test passes 100 derandomized examples with zero disagreements, your timeit re-run shows the list beating the matrix by two orders of magnitude on the same seeded graph, and both unseen problems ship with a checker, not just an answer.
Mark passed, then open 3.9 Only mark this when you can do it without notes.Leads to
- 3.9 Flow and matching at recognition depth Carry the checker habit into matching: a cut of equal value certifies a flow.
- 5.8 Recurrence proofs and differential validation Apply the same oracle discipline to recurrences: brute force on small instances first.
Comes after
- 3.5 Union-find with path compression and union by rankComponent counts need the find-then-count discipline, which the validation unit turns into checkers.
- 3.7 Minimum spanning trees with Kruskal and PrimVerify your MST against brute force on \(n \le 8\) before trusting the greedy.
Resources for this unit
- Algorithms - graph chapters Use the basic graph, depth-first search, minimum spanning tree, shortest path and flow chapters, and lecture note 11 Disjoint Sets for union-find, for correctness proofs and counterexamples to tempting wrong algorithms.
- Hypothesis - generated graph tests Generate small sparse, dense, disconnected, cyclic, parallel-edge and weighted graphs. Compare optimized results with exhaustive or deliberately simple references and retain shrunk failures.
Also in this section
- DSA Handbook - graphs Study all of Part 8 in order. For each algorithm, write the representation, invariant, forbidden input assumptions and independently checkable output before reading the implementation.
- AlgoMaster DSA - graph slice Attempt Number of Islands, Course Schedule II and Network Delay Time cold. They cover traversal, dependency modeling and weighted shortest paths; add one narrative problem only if graph modeling remains weak.
- NeetCode - unseen graph problems Use two unseen story problems without graph tags. Grade the model, assumptions, certificate and tests as well as the final answer.