The GraphSCCFn functor

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 = Nd

Arguments

Nd: ORD_KEY
  • Nd : ORD_KEY:: The argument structure Nd defines 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 list

Description

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, or RECURSIVE, consisting of a list of nodes that are all connected by cyclic paths. A single node with a self loop is represented by the RECURSIVE constructor.

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 the roots list.

val topOrder : { root: node, follow: node -> node list } -> component list

topOrder {root, follow} is equivalent to the expression

topOrder' {roots = [root], follow = follow}

See Also