containers-0.5.11.0: Assorted concrete container types

Data.Graph

Description

A version of the graph algorithms described in:

Structuring Depth-First Search Algorithms in Haskell, by David King and John Launchbury.

Synopsis

# External interface

Arguments

 :: Ord key => [(node, key, [key])] The graph: a list of nodes uniquely identified by keys, with a list of keys of nodes this node has edges to. The out-list may contain keys that don't correspond to nodes of the graph; such edges are ignored. -> [SCC node]

The strongly connected components of a directed graph, topologically sorted.

Arguments

 :: Ord key => [(node, key, [key])] The graph: a list of nodes uniquely identified by keys, with a list of keys of nodes this node has edges to. The out-list may contain keys that don't correspond to nodes of the graph; such edges are ignored. -> [SCC (node, key, [key])] Topologically sorted

The strongly connected components of a directed graph, topologically sorted. The function is the same as stronglyConnComp, except that all the information about each node retained. This interface is used when you expect to apply SCC to (some of) the result of SCC, so you don't want to lose the dependency information.

data SCC vertex Source #

Strongly connected component.

Constructors

 AcyclicSCC vertex A single vertex that is not in any cycle. CyclicSCC [vertex] A maximal set of mutually reachable vertices.
Instances