Shortcut sets for reachability
Add directed edges while preserving which vertices are reachable from each source.
Graph algorithms for Python
Graph reachability,
queryable.
reachq is a focused Python library for building exact reachability shortcut sets and weighted shortest-path hopsets on directed graphs. It makes the construction, query, and verification steps explicit.
MIT licensedPython 3.10–3.13Pre-1.0
REACHQ / QUERY PATH explicit
Project status
Pre-1.0, source-first, research-aware.
The core API is usable and tested, but compatibility is not promised before 1.0. Install from a source checkout and read the explicit limits before adoption.
01 / Install
Start from a clean
source checkout.
Keeping the code, tests, examples, and docs on one commit makes the current behavior inspectable.
$ git clone https://github.com/sachncs/reachq && cd reachq && pip install -e ".[dev]"
Python 3.10–3.13NumPy ≥ 1.21SciPy ≥ 1.10
02 / Minimal working example
Build a shortcut set.
Then prove it.
The first example does not promise a speedup. It constructs a result, checks exact reachability preservation, and makes the realized bound visible.
InputA deterministic directed graph.
ConstructionShortcuts plus beta and realised bound.
InvariantOriginal and augmented reachability agree.
from reachq.generators import random_dag
from reachq.shortcut import build_shortcut_set_for_reachability
from reachq.invariants import assert_reachability_preserved
graph = random_dag(n=100, edge_probability=0.1, random_seed=42)
shortcuts, beta, realised_bound = build_shortcut_set_for_reachability(
graph, omega=3.0, random_seed=42
)
assert_reachability_preserved(graph, shortcuts)What reachq does
Two constructions.
One clear boundary.
Use reachq when the graph algorithm itself is the work: precompute structure, run a bounded query, and check the result against an explicit invariant.
Hopsets for weighted paths
Add weighted links and query with a hop limit while keeping epsilon visible.
Checks close to the code
Seeds, bounds, serialization, and invariants make algorithmic experiments inspectable.
03 / How it works
Construct once.
Measure what follows.
The library separates construction from querying so you can compare setup cost, query cost, memory, and correctness on your own graph family.
Exact relation
Shortcut sets
Build H, query G ∪ H, and verify that reachability is unchanged.
G+H→same reachability
Read the conceptBounded query
Hopsets
Build weighted links, query with max_hops, and compare distances with exact Dijkstra.
G+Hw→epsilon is explicit
Read the concept04 / Read the contract
Useful because
the limits are visible.
Formal results, implementation behavior, and measured performance are different kinds of evidence. The docs keep them separate.
Exact preservation
Shortcut workflows expose an invariant for the reachable relation.
Explicit epsilon
Hopset checks compare bounded paths with an exact baseline.
Seeded runs
Insertion order and random seeds support reproducible experiments.
Visible limits
No blanket speedup, hosted service, or pre-1.0 compatibility promise.
05 / Documentation
Start with the concept.
Then inspect the implementation.
The docs are organized by the question you are trying to answer: install, understand, build, reference, research, or contribute.
01
Getting started
Install and run the first verified construction.
Start here →02API reference
Find the supported graph, query, configuration, and invariant surface.
Browse API →03Concepts
Understand shortcut sets, hopsets, correctness, and limitations.
Understand the model →04Benchmarks
Record the context needed to make a result reproducible.
Measure honestly →05Research
Separate paper provenance from current implementation behavior.
Read the boundary →06Contributing
Set up the project and make changes that stay maintainable.
Join the work →06 / Provenance
Research depth,
product clarity.
The constructions are informed by published graph-algorithm research. reachq keeps literature results, implementation facts, and benchmark observations distinct.
Read the provenance0.9development snapshot
2core constructions
1explicit boundary