The GraphSCCFn functor implements an algorithm for
calculating the strongly-connected components of a directed graph.
The resulting components are topologically-sorted; i.e., if a component
A comes before a component B in the result, then there is no
path from B to A (but there might be a path from A to B).
Synopsis
functor GraphSCCFn (Nd: ORD_KEY) :> GRAPH_SCC where Nd = NdArguments
Nd: ORD_KEY-
Nd : ORD_KEY:: The argument structureNddefines the type of graph nodes paired with a comparison function that is used by the algorithm to implement finite maps keyed by nodes.
Interface
structure Nd : ORD_KEY
type node = Nd.ord_key
datatype component
= SIMPLE of node
| RECURSIVE of node list
val topOrder' : { roots: node list, follow: node \-> node list } -> component list
val topOrder : { root: node, follow: node \-> node list } -> component listDescription
structure Nd : ORD_KEY-
The argument structure.
type node = Nd.ord_key-
The type of a node in the graph.
datatype component-
The type of a component in the result. Components are either
SIMPLE, consisting of a single node, orRECURSIVE, consisting of a list of nodes that are all connected by cyclic paths. A single node with a self loop is represented by theRECURSIVEconstructor. val topOrder': { roots: node list, follow: node -> node list } -> component list-
topOrder{roots, follow}` returns a topologically-sorted list of strongly-connected components for a directed graph. The graph is specified by a list of root nodes and a follow (or successor) function that returns the list of successors for a node. The first component in the result will contain the first node in therootslist. val topOrder : { root: node, follow: node -> node list } -> component list-
topOrder {root, follow}is equivalent to the expression
topOrder' {roots = [root], follow = follow}