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.