Getting started
Install reachq from source, build your first shortcut set, and verify the result against the library's explicit invariants.
Install from source
reachq is pre-1.0 and is not published to PyPI yet. Keeping installation tied to a repository commit makes the examples, tests, and implementation unambiguous.
git clone https://github.com/sachncs/reachq
cd reachq
python -m pip install -e ".[dev]"Build and verify a shortcut set
A shortcut set augments a directed graph with additional edges while preserving exact reachability. The assertion is the important part of this first example: it checks the contract instead of implying a speedup.
from reachq.generators import random_dag
from reachq.invariants import assert_reachability_preserved
from reachq.shortcut import build_shortcut_set_for_reachability
graph = random_dag(n=1000, edge_probability=0.1, random_seed=42)
shortcuts, beta, bound = build_shortcut_set_for_reachability(
graph, omega=3.0, random_seed=42,
)
assert_reachability_preserved(graph, shortcuts)
print(len(shortcuts), beta, bound)Build a weighted hopset
Hopsets target bounded-hop shortest-path queries. The epsilon budget is explicit; compare the result with an exact Dijkstra baseline for the graph and workload you care about.
from reachq import WeightedDigraph
from reachq.hopset import build_hopset_for_sssp
from reachq.invariants import assert_distance_approximation
graph = WeightedDigraph()
graph.add_edge("a", "b", 1)
graph.add_edge("b", "c", 2)
graph.add_edge("a", "c", 10)
hopset, beta = build_hopset_for_sssp(graph, epsilon=0.1, random_seed=42)
assert_distance_approximation(graph, hopset, source="a", epsilon=0.1, max_hops=20)Current boundary: the core is pure Python, the reachability construction can opt into process-level work, and the hopset path is currently sequential. Read the limitations before adopting it.