GHC.Data.Graph.Directed.Reachability

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.

If you need a topologically sorted list, consider using the functions exposed from GHC.Data.Graph.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 GHC.Data.Graph.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

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.

By partially applying this function to a set of roots, the resulting function can be applied many times and share the initial work.

Properties: * No self loops, i.e. isReachableMany _ [a] a == False