graph/reachability_utils library
Transitive closure / reachability of a directed graph (roadmap #551).
Answers "which nodes can node i eventually get to" by running a traversal from every node. A node appears in its OWN reachable set only when it lies on a cycle (there is a non-trivial path leading back to itself), since reachability here means "via one or more edges", never the trivial zero-hop.
Functions
-
canReach(
Adjacency graph, int from, int to) → bool -
Whether node
tois reachable from nodefromvia one or more edges. -
reachabilityMatrix(
Adjacency graph) → List< List< bool> > - Boolean reachability matrix consistent with reachabilitySets.
-
reachabilitySets(
Adjacency graph) → List< Set< int> > - For each node, the set of nodes reachable from it via one or more edges.