Moduleghc-9.14.1GHC2021

GHC.Data.Graph.Directed.Reachability

An abstract interface for a fast reachability data structure constructed from a GHC.Data.Graph.Directed graph.

1 type
7 values

Packageghc-9.14.1
Exports8
LanguageGHC2021
LicenceBSD-3-Clause
SourceReachability.hs

datadata ReachabilityIndex node

The abstract data structure for fast reachability queries

Constructing a reachability index

2 declarations

valuegraphReachability :: Graph node -> ReachabilityIndex node

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

valuecyclicGraphReachability :: Graph node -> ReachabilityIndex node

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.

Reachability queries

4 declarations

valueallReachable

:: ReachabilityIndex node
-> node
The root node
-> [node]
All nodes reachable from root

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.

valueallReachableMany

:: ReachabilityIndex node
-> [node]
The roots
-> [node]
All nodes reachable from all roots

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).

valueisReachable

:: ReachabilityIndex node
```
g
```
-> node
```
a
```
-> node
```
b
```
-> Bool
b is reachable from a

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

valueisReachableMany

:: ReachabilityIndex node
```
g
```
-> [node]
```
roots
```
-> node
b is reachable from any of the roots
-> Bool

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

Debugging

1 declaration

valuereachabilityIndexMembers :: ReachabilityIndex node -> [node]