Module Data.SCC

Computing strongly connected components

Copyright (c) 2000 - 2003, Wolfgang Lux See LICENSE for the full license.

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]]  Deterministic 
Computes the strongly connected components of a list of entities.

Exported operations:

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

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