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}``