Make an algorithm check include its invalid inputs
Does a shortest-path implementation return known distances and reject inputs outside its assumptions?
Make this plan your own ↓Read, edit and export without an account. This is preparation; no run or result is claimed.
Make the question your own.
5 sources · Exact preparation context
- Small shortest-path solvers with negative-weight controls →
Original local preparation by the Executable Science seed collection; upstream API references remain separately attributed.
Record revision: d26927f9f38bad90e327ec591cba796251b9a586ffa5809ca251bf138df2a943
- NetworkX →
Preserve the upstream project name, version, repository link, applicable notices, and contributor attribution when preparing an artifact for reuse.
Record revision: f19cb5f6024cf6cae473beae60430962181062f6085fe3c3df6384b0d09564f9
- Compressed Sparse Graph Routines (scipy.sparse.csgraph) →
SciPy documentation. Compressed Sparse Graph Routines (scipy.sparse.csgraph). https://docs.scipy.org/doc/scipy-1.18.0/tutorial/csgraph.html; observed version 1.18.0.
Record revision: 899da7c252b3ca513fd6d2f8eed17980cfd042eb15e4aae30fdbdde88189d656
- [Re] Speedup Graph Processing by Graph Ordering →
Lécuyer, Fabrice; Danisch, Maximilien; Tabourier, Lionel. [Re] Speedup Graph Processing by Graph Ordering. ReScience C 7(1), #3; 10.5281/zenodo.4836230.
Record revision: 1d4cc94669701d57248cbb2f55a1f14ad014a73b5d8a963ee0dce0c3a5c24b6d
- Hypothesis →
Preserve the upstream project name, version, repository link, applicable notices, and contributor attribution when preparing an artifact for reuse.
Record revision: b391cd8285f077d9e64ab0add10edbf759da980506401721e52bce5c299c8ac7
Source links open the current listing. This plan retains the revisions above; listing review does not grant permission to copy or adapt source files.
Before carrying out this plan
- The original fixed example is prepared for isolated standard-library execution.
- NetworkX/SciPy/Hypothesis dependency environments remain unqualified for this collection.
Limits to keep in view
- A few examples cannot establish general correctness or a speedup.
- Do not execute source repositories on the developer host.
Edit freely. Export a copy before reloading or leaving. Your text stays in this tab until you choose to copy, download or save it privately.
What to compare
The pilot contains three small controls. Broader properties need a stated generator, input contract, qualified environment and independently specified checks.
Useful outputs
- Hand-enumerated distances for the fixed small graph.
- Explicit negative-edge and reachable-negative-cycle controls.
- An extension plan separating algorithm correctness from graph-ordering performance.
Inputs and prerequisites
- The original fixed example is prepared for isolated standard-library execution.
- NetworkX/SciPy/Hypothesis dependency environments remain unqualified for this collection.
What this work would not establish
- A few examples cannot establish general correctness or a speedup.
- Do not execute source repositories on the developer host.
Start with these sources.
Small shortest-path solvers with negative-weight controls
Executable Science local pilot drafts
Provide Dijkstra and Bellman–Ford implementations with hand-enumerated reference graphs, explicit negative-edge rejection, and a negative-cycle control.
Investigate Do the implementations respect their input assumptions and return the expected distances on the supplied controls?
NetworkX
Upstream project repository
Graph construction, traversal, structural analysis, and network algorithms in Python.
Investigate Do weighted shortest-path routines match exhaustive simple-path enumeration on bounded positive-weight graphs?
Compressed Sparse Graph Routines (scipy.sparse.csgraph)
SciPy documentation
A tutorial on algorithms for graphs represented as sparse matrices, illustrated through path finding.
Investigate Do sparse-graph path computations agree with exact enumeration on tiny weighted graphs containing disconnected components?
[Re] Speedup Graph Processing by Graph Ordering
ReScience C
A C++ replication about graph ordering as a way to change graph-processing performance.
Investigate Does a chosen ordering preserve algorithm outputs while improving measured performance across graph families?
Hypothesis
Upstream project repository
Property-based testing tools that generate and simplify test inputs.
Investigate Can a fixed property-based test expose a specified floating-point overclaim within a bounded search protocol?