

Safe HaskellNone




Graph algorithms in the ST monad.



data Graph s a Source

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.

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


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

SCC Computation

data SCC a Source


AcyclicSCC a 
CyclicSCC [a] 


Eq a => Eq (SCC a) 
Show a => Show (SCC a) 

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.