Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
package tsort
Topological sort
val sort : ('a * 'a list) list -> 'a sort_resultPerform 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).