Safe Haskell | None |
---|

Graph algorithms in the ST monad.

- data Graph s a
- newGraph :: (Eq a, Hashable a) => [a] -> [(a, a)] -> ST s (Graph s a)
- newGraphNoDupeNodes :: (Eq a, Hashable a) => [a] -> [(a, a)] -> ST s (Graph s a)
- successorNodes :: (Eq a, Hashable a) => Graph s a -> a -> ST s [a]
- data SCC a
- = AcyclicSCC a
- | CyclicSCC [a]

- sccs :: (Eq a, Hashable a) => Graph s a -> ST s [SCC a]
- nonReflexiveRepresentativesForNodes :: (Eq a, Hashable a) => Graph s a -> ST s [(a, a)]

# Documentation

A graph of `a`

s in the state thread s.

We store the successors in an unboxed array and store indexes into the array for the index at which at a node's successors start. This is very memory efficient and cache friendly.

# SCC Computation

sccs :: (Eq a, Hashable a) => Graph s a -> ST s [SCC a]Source

An optimised implementation of Tarjan's SCC algorithm.

# Relation Tools

nonReflexiveRepresentativesForNodes :: (Eq a, Hashable a) => Graph s a -> ST s [(a, a)]Source

Given a graph, computes the transitive (but not reflexive) closure of the graph and then returns the relation (a,b) such that b is the representative member for a. Note, no pairs of the form a == b are returned, even if there is an edge from a to b. This is to minimise the size of the transitive closure.