Data.Graph.ST

Graph algorithms in the ST monad.

Documentation

data Graph s 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.

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]

SCC Computation

data SCC a

Constructors

AcyclicSCC a

CyclicSCC [a]

Instances

Eq a => Eq (SCC a)

Show a => Show (SCC a)

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

An optimised implementation of Tarjan's SCC algorithm.

Relation Tools

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

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.