uulib-0.9.8: Haskell Utrecht Tools Library






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,[])]

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.