Compute the strongly connected components of a directed graph. The implementation is based on the following article:

• David King and John Launchbury, Lazy Depth-First Search and Linear Graph Algorithms in Haskell, ACM Principles of Programming Languages, San Francisco, 1995.

In contrast to their description, this module doesn't use lazy state threads but is instead purely functional -- using the Map and Set module. This means that the complexity of scc is O(n*log n) instead of O(n) but due to the hidden constant factor, this implementation performs very well in practice.

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.