The abstract data structure for fast reachability queries

Construct a ReachabilityIndex from an acyclic Graph. If the graph can have cycles, use cyclicGraphReachability

Construct a ReachabilityIndex from a Graph which may have cycles. If this reachability index is just going to be used once, it may make sense to use reachablesG instead, which will traverse the reachable nodes without constructing the index -- which may be faster.

allReachable returns the nodes reachable from the given root node.

Properties: * The list of nodes does not include the root node! * The list of nodes is deterministically ordered, but according to an internal order determined by the indices attributed to graph nodes. * This function has $O(1)$ complexity.

If you need a topologically sorted list, consider using the functions exposed from Directed on Graph instead.

allReachableMany returns all nodes reachable from the many given roots.

Properties: * The list of nodes does not include the roots node! * The list of nodes is deterministically ordered, but according to an internal order determined by the indices attributed to graph nodes. * This function has $O(n)$ complexity where $n$ is the number of roots.

If you need a topologically sorted list, consider using the functions exposed from Directed on Graph instead (reachableG).

Fast reachability query.

On graph g with nodes a and b, isReachable g a b asks whether b can be reached through g starting from a.

Properties: * No self loops, i.e. isReachable _ a a == False * This function has $O(1)$ complexity.

Fast reachability query with many roots.

On graph g with many nodes roots and node b, isReachableMany g as b asks whether b can be reached through g from any of the roots.

Properties: * No self loops, i.e. isReachableMany _ [a] a == False * This function is $O(n)$ in the number of roots