# Documentation

scc :: Ord v => [(v, [v])] -> [[v]]Source

Compute the strongly connected components of a graph. The algorithm is tailored toward the needs of compiler writers that need to compute recursive binding groups (for example, the original order is preserved as much as possible).

The expression (`scc xs`

) computes the strongly connectected components
of graph `xs`

. A graph is a list of nodes `(v,ws)`

where `v`

is the node
label and `ws`

a list of nodes where `v`

points to, ie. there is an
arrow/dependency from `v`

to each node in `ws`

. Here is an example
of `scc`

:

Scc\> scc [(0,[1]),(1,[1,2,3]),(2,[1]),(3,[]),(4,[])] [[3],[1,2],[0],[4]]

In an expression `(scc xs)`

, the graph `xs`

should contain an entry for
every node in the graph, ie:

all (`elem` nodes) targets where nodes = map fst xs targets = concat (map snd xs)

Furthermore, the returned components consist exactly of the original nodes:

sort (concat (scc xs)) == sort (map fst xs)

The connected components are sorted by dependency, ie. there are no arrows/dependencies from left-to-right. Furthermore, the original order is preserved as much as possible.