Library

Module

Module type

Parameter

Class

Class type

Topological sort

`val sort : ('a * 'a list) list -> 'a sort_result`

Perform a normal topological sort on a directed acyclic graph (DAG).

The result is in "dependency order", i.e. if there's an edge from A to B, then B comes first. For example, `sort [1, [2]; 2, []]`

returns `[2; 1]`

.

If your graph may contain legitimate cycles, consider using `sort_strongly_connected_components`

instead.

Missing nodes such as node 2 in graph `[1, [2]]`

are automatically added, resulting in the graph `[1, [2]; 2, []]`

. If this is undesirable, consider running `find_nonexistent_nodes`

on the input graph.

Perform a topological sort on a directed graph that may have cycles. Uses `find_strongly_connected_components`

and `sort`

.

Like with `sort`

, missing nodes are silently added to the graph.

For example, ```
find_strongly_connected_components
["A", ["B"]; "B", ["C"]; "C", ["B"; "D"]]
```

returns `["D"]; ["B"; "C"]; ["A"]`

.

Report nodes that have non-existent dependencies. This is useful for detecting user-entry errors, since the other functions of the module silently add missing nodes to the graph.

The result is an assoc list where the keys are nodes with bad dependencies, and values are lists of nodes not found among the original assoc list keys.

For example, `find_nonexistent_nodes ["test", ["biuld"]; "build", []]`

returns `"test", ["biuld"]`

.

Partition a graph into its strongly-connected components: Two vertices u, v belong to the same component iff there's a path from u to v and there's a path from v to u.

See https://en.wikipedia.org/wiki/Strongly_connected_component

The current implementation uses the Kosaraju-Sharir algorithm, which is described at https://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

The theoretical complexity of the Kosaraju-Sharir algorithm is O(n) = O(|V|+|E|) but due to the use of resizable hash tables and a final sorting pass, the complexity of this implementation is O(n log n).