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
- sccs :: (Eq a, Hashable a) => Graph s a -> ST s [SCC a]
- nonReflexiveRepresentativesForNodes :: (Eq a, Hashable a) => Graph s a -> ST s [(a, a)]
A graph of
as 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.
An optimised implementation of Tarjan's SCC algorithm.
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.