Module Data.SCC

Computing strongly connected components

The function scc computes the strongly connected components of a list of entities in two steps. First, the list is topologically sorted "downwards" using the defines relation. Then the resulting list is sorted "upwards" using the uses relation and partitioned into the connected components. Both relations are computed within this module using the bound and free names of each declaration.

In order to avoid useless recomputations, the code in the module first decorates the declarations with their bound and free names and a unique number. The latter is only used to provide a trivial ordering so that the declarations can be used as set elements.

Author: Wolfgang Lux

Summary of exported operations:

scc
                  :: (Eq a, Eq b) => (a -> [b]) -> (a -> [b]) -> [a] -> [[a]]

Computes the strongly connected components of a list of entities.

Exported operations:

scc :: (Eq a, Eq b) => (a -> [b]) -> (a -> [b]) -> [a] -> [[a]]

Computes the strongly connected components of a list of entities. To be flexible, we distinguish the nodes and the entities defined in this node.

Example call:: (scc defines uses nodes)

Parameters:

defines : maps each node to the entities defined in this node
uses : maps each node to the entities used in this node
nodes : the list of nodes which should be sorted into strongly connected components

Returns:: the strongly connected components of the list of nodes