Shortcut sets
A shortcut set adds directed edges so reachability can be queried on an augmented graph without changing the reachable relation.
Model
Given a directed graph G, the construction returns a set H of directed pairs. Queries operate on G ∪ H; the preservation invariant checks that every source reaches the same vertices as it did in G.
Construction
build_shortcut_set_for_reachability handles cyclic input through strongly connected components and then constructs shortcuts over the resulting structure. The returned realised bound is derived from the executed recursion, not inferred from a benchmark.
Query
Use bfs_reachability for the original graph and parallel_bfs with shortcut_edges for the augmented traversal. Always validate the invariant for the graph family and parameters you care about.