Reachability

Canonical workflow

from reachq.generators import random_dag
from reachq.invariants import assert_reachability_preserved
from reachq.reachability import bfs_reachability, parallel_bfs
from reachq.shortcut import build_shortcut_set_for_reachability

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)
source = graph.vertices()[0]
assert parallel_bfs(graph, source, shortcuts) == bfs_reachability(graph, source)

What the return values mean

• shortcuts is a set of directed vertex pairs.
• beta is the asymptotic target quantity used by the construction.
• realised_bound is the bound derived by the executed recursion and is the value tests should use.

parallel_bfs currently simulates the reachability primitive sequentially. Construction-level process dispatch is opt-in and should be benchmarked for the graph size at hand.