reachq: graph reachability, queryable.
Pure-Python reimplementation of the JLS shortcut-set and CFR hopset constructions, with seven toggleable algorithmic refinements and four documented correctness fixes.
A pure-Python reimplementation of two parallel graph algorithms from:
"Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth" Ashvinkumar, Bernstein, Probst Gutenberg, Saranurak. arXiv:2605.03892.
See docs/INSPIRED_BY.md for the full disclaimer
about the relationship between reachq and the cited papers.
It also contains contributions layered on top of the cited work:
docs/PAPER.md— the unified paper draft (historical; current claims about StreamingShortcutSet and greedy_shortcut_set do not match the implementation; seedocs/limitations.md).docs/notes_correctness.md— a corrigendum documenting four bugs found and fixed in the reference implementation.docs/spectral_fixtures.md— test fixtures from Papers 2/3 (SRG, Hamming, Paley, Petersen).docs/fix_resample.md— experimental Fix/Resample variant from Paper 1.
Use reachq when you want a Python library that:
- Computes shortcut sets for parallel reachability.
- Computes hopsets for approximate shortest paths.
- Has reproducible benchmarks and tests.
If you want a general-purpose graph library with full algorithms
(BFS, Dijkstra, SCC, etc.), use networkx or igraph and call
reachq only for the specific parallel-reachability shortcuts.
| feature | reachq | networkx | igraph |
|---|---|---|---|
| JLS shortcut set | yes | no | no |
| CFR hopset | yes | no | no |
| beta-hopbound-preserving sparsification | yes (small graphs) | no | no |
| streaming shortcut set | experimental prototype (no formal bound) | no | no |
| (1+ε) approximation | vanilla greedy (no formal guarantee) | no | no |
| full graph library | no (focused) | yes | yes |
| reproducible benchmarks | yes | partial | no |
pip install reachq
# or
git clone https://github.com/sachncs/parallel-reachability-and-shortest-paths
cd parallel-reachability-and-shortest-paths
pip install -e ".[dev]"Requirements: Python ≥ 3.10, numpy ≥ 1.21, scipy ≥ 1.10.
No JIT, no native extensions; the wheel is pure-Python.
from reachq.core.algorithm import build_shortcut_set_for_reachability
from reachq.core.generators import random_dag
from reachq.core.reachability import bfs_reachability, parallel_bfs
g = random_dag(n=1000, edge_probability=0.1, random_seed=42)
shortcuts, beta = build_shortcut_set_for_reachability(g, omega=3.0, random_seed=42)
src = next(iter(g.vertices()))
assert bfs_reachability(g, src) == parallel_bfs(g, src, shortcuts)Disable any refinement:
from reachq import RefinementConfig
shortcuts, beta = build_shortcut_set_for_reachability(
g,
omega=3.0,
random_seed=42,
flags=RefinementConfig(enable_tc_pruning=False, tight_tc_trigger=True),
)Five more end-to-end applications live in examples/:
gnn_preprocessing.py— citation graph → PyG Data object.rag_reranking.py— passage-citation graph → pivot-reach ranking.compiler_inlining.py— IR graph → inlining candidate ranking.social_network.py— SNAP cit-HepPh →|H|/|E|ratio.bioinformatics.py— synthetic PPI → downstream-hub detection.
The seven toggles on RefinementConfig (re-exported as
reachq.Flags); all default to on except parallel.
| Flag | Effect |
|---|---|
adaptive_sampling |
Adapt per-level sampling probability from observed part sizes. |
label_compress |
Store labels as frozenset[int] instead of set[str]. |
skip_condense |
Skip SCC condensation on DAG inputs. |
hop_bounded_bfs |
Use a hop-bounded BFS kernel in the pivot loop. |
degree_ordered_pivots |
Process pivots in ascending out-degree order. |
tight_tc_trigger |
Tighten the TC-pruning trigger by work comparison. |
skip_trivial_part |
Skip recursion when the partition is a single part. |
enable_tc_pruning |
Enable TC-pruning (Theorem 2's improvement). |
parallel |
Reserved; the current implementation is sequential. |
The parallel_workers parameter on both wrappers is accepted for
API symmetry; the current implementation is sequential.
See docs/algorithms.md §"Refinement flags"
and docs/limitations.md.
pytest # 575 passed + 1 xfailed (576 total)
pytest -m "not slow" # skip slow tests
pytest --cov=reachq # with coverage (currently 76%)The lemma tests run 50 random seeds per invariant claim; failures would indicate the lemmas don't hold empirically on the tested graph class.
The current test count is in CHANGELOG.md; do
not hard-code counts in user-facing docs.
from reachq import RefinementConfig as Flags, Digraph, WeightedDigraph
from reachq.core.algorithm import (
build_shortcut_set_for_reachability, # Theorem-2 wrapper
jls_with_tc_pruning, # direct recursion
jls_shortcut_set, # wrapper, TC pruning off
)
from reachq.core.hopset import (
build_hopset_for_sssp, # Theorem-4 wrapper
cfr_with_truncsssp_pruning, # direct recursion
cfr_hopset, # wrapper, TruncSSSP off
)
from reachq.core.reachability import (
bfs_reachability,
parallel_bfs,
strongly_connected_components,
topological_sort,
)
from reachq.core.shortest_paths import (
dijkstra,
shortest_path_hopbound,
truncated_dijkstra,
compute_d_ball,
compute_d_ancestors,
compute_d_descendants,
)
from reachq.core.tc import (
transitive_closure_matrix,
transitive_closure_brute_force,
)
from reachq.core.generators import (
random_dag,
weighted_random_dag,
layered_dag,
dense_graph,
graph_with_sccs,
path_graph,
cycle_graph,
grid_graph,
petersen_graph,
paley_graph,
shrikhande_graph,
shrikhande_cayley,
hamming_graph,
)
from reachq.core.io.json import (
dump, # digraph -> JSON string
load, # JSON string -> digraph
weighted_dump,
weighted_load,
)Full API reference: docs/REFERENCE.md (auto-
generated by mkdocstrings from the actual signatures).
parallel-reachability-and-shortest-paths/
├── reachq/ # Main package
│ ├── __init__.py # Public API + __version__
│ ├── core/ # Always-imported library layer
│ │ ├── algorithm.py # JLS + TC-pruning (Theorem 2)
│ │ ├── bfs.py # Vectorised CSR BFS
│ │ ├── config.py # RefinementConfig + logging
│ │ ├── csr.py # CSR pair builder
│ │ ├── generators.py # Deterministic generators + SNAP loader
│ │ ├── graph.py # Digraph, WeightedDigraph
│ │ ├── hopset.py # CFR + TruncSSSP-pruning (Theorem 4)
│ │ ├── invariants.py # Theorem-oriented validators
│ │ ├── io/ # JSON + Arrow + NetworkX
│ │ ├── metrics.py # Opt-in counters and histograms
│ │ ├── predictor.py # Heuristic graph-property estimators
│ │ ├── prune.py # TC-pruning (extracted)
│ │ ├── reachability.py # BFS, SCC, topological sort
│ │ ├── shortest_paths.py # Dijkstra, A*, truncated SSSP
│ │ ├── snapshot.py # Frozen graph snapshot dataclass
│ │ ├── spectrum.py # Eigenvalues and spectral gap
│ │ ├── tc.py # Sparse Boolean matmul TC
│ │ ├── trace.py # Contextmanager tracing
│ │ ├── tuner.py # auto_tune RefinementConfig
│ │ ├── work_depth.py # PRAM work/depth accounting
│ │ └── backends/ # Backend Protocol + ParallelContext
│ ├── research/ # Opt-in refinements (off-paper)
│ ├── accel/ # Experimental Cython/Rust/Numba (see docs/accel.md)
│ ├── cli/ # Console-script entry point
│ └── proto/ # Duck-typed Protocols
├── tests/ # 576 tests
├── scripts/ # CLI / benchmark / reproduction
├── docs/ # 24 docs (see docs/index.md)
├── examples/ # 5 end-to-end applications
├── benchmarks/ # asv micro-benchmarks
├── pyproject.toml
├── CHANGELOG.md
├── CONTRIBUTING.md
├── CODE_OF_CONDUCT.md
├── SECURITY.md
├── README.md
└── LICENSE
The docs list is in docs/index.md. See also
docs/architecture.md for the per-module
responsibility table.
pip install -e ".[dev]"
mkdocs build --strict # verify the docs build cleanly
mkdocs serve # preview at http://127.0.0.1:8000The documentation site is built by CI on every PR but is not yet deployed to GitHub Pages (see the Roadmap).
Notable entry points:
docs/START_HERE.md— three routing paths (use / understand / extend).docs/getting-started.md— install + first construction.docs/algorithms.md— algorithm descriptions, parameter selection, RefinementConfig flags.docs/architecture.md— module responsibilities- dependencies.
docs/REFERENCE.md— full API reference.docs/limitations.md— what is NOT implemented.docs/GLOSSARY.md— terminology.
See docs/limitations.md for the consolidated
list. The short version:
- No true parallel execution. Single-threaded;
parallel_workersis accepted for API symmetry but logged-and-ignored on the process path. - No JIT / no native extensions. Pure-Python wheel; the
experimental Cython/Rust kernels in
reachq/accel/are not built or shipped. - No formal (1+ε) approximation.
greedy_shortcut_setis a vanilla greedy. - No amortised streaming bound.
StreamingShortcutSetis a prototype; the O(log² n) per-insertion bound is not implemented. web-Google(n=875k) is out of reach for single-process Python.
- Cython port of the per-pivot BFS inner loop (for
web-Google-scale inputs) — scaffolding exists under
reachq/accel/but is not built or shipped (seedocs/accel.md). - Deploy the MkDocs site to GitHub Pages.
- Publish the cibuildwheel wheels to PyPI (
release.ymlcurrently publishes only the sdist).
- PRAM span for the actual parallel runtime (requires a
real PRAM model;
SpanProfilermeasures sequential phases only).
See CONTRIBUTING.md. For research questions, see
docs/PAPER.md for what's been proved and what's
empirical.
@article{ashvinkumar2026parallel,
title={Parallel Reachability and Shortest Paths on Non-sparse Digraphs:
Near-linear Work and Sub-square-root Depth},
author={Ashvinkumar, Vikrant and Bernstein, Aaron and
Probst Gutenberg, Maximilian and Saranurak, Thatchaphol},
journal={arXiv preprint arXiv:2605.03892},
year={2026}
}For the refinements in this implementation:
@misc{reachq2026refinements,
title={Algorithmic refinements for parallel reachability:
tightened TC-pruning and hop-bounded pivot BFS},
author={reachq contributors},
year={2026},
howpublished={\url{https://github.com/sachncs/parallel-reachability-and-shortest-paths}}
}MIT © 2026 Sachin