# package tsort

Easy to use and user-friendly topological sort

## Sources

2.0.0.zip
`md5=78f0b6c5855b303e5f9911cceaabd089`
`sha512=6ad3c789ca0230948fd8f20352940ea6a6e7948403aa3dc1660ca8e7dba40062f30eca542353fba8d3b20c4808431bd796ecba7476283993b93b5f13e25f475e`

## Description

Easy to use and user-friendly topological sort.

Example:

``````Tsort.sort [("foundation", []); ("walls", ["foundation"]); ("roof", ["walls"])]
``````

## ocaml-tsort

This module provides topological sort based on Kahn's algorithm. It's not very fast, but it's easy to use and provides friendly error reporting.

It works on assoc lists (`('a * 'a list) list`). The keys are "tasks" and the values are lists of their dependencies.

## Sorting DAGs

Most of the time cyclic dependencies are bad. The main function, `Tsort.sort` returns value of this type:

``````type 'a sort_result =
Sorted of 'a list
| ErrorCycle of 'a list
``````

The function is:

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

Examples:

``````# Tsort.sort [("foundation", []); ("walls", ["foundation"]); ("roof", ["walls"])] ;;
- : string Tsort.sort_result = Tsort.Sorted ["foundation"; "walls"; "roof"]

# Tsort.sort [("foundation", ["building permit"]); ("walls", ["foundation"]); ("roof", ["walls"])] ;;
- : string Tsort.sort_result =
Tsort.Sorted ["building permit"; "foundation"; "walls"; "roof"]

# Tsort.sort [("foundation", ["roof"]); ("walls", ["foundation"]); ("roof", ["walls"])] ;;
- : string Tsort.sort_result = Tsort.ErrorCycle ["roof"; "foundation"; "walls"]
``````

As you can see from the second example, if there's a dependency on a node that doesn't exist in the assoc list keys, it's automatically inserted, and assumed to have no dependencies.

## Detecting non-existent dependencies

If your graph comes directly from user input, there's a good chance that dependency on a non-existent node is a user error.

To prevent it, use `Tsort.find_nonexistent_nodes`. Example:

``````# Tsort.find_nonexistent_nodes [("foundation", ["building permit"]); ("walls", ["foundation"]); ("roof", ["walls"])] ;;
- : (string * string list) list = [("foundation", ["building permit"])]
``````

## Sorting graphs with cycles

Sometimes cycles are fine. In this case you can use `Tsort.sort_strongly_connected_components` to split your graph into strongly connected components and sort its condensation.

Contrived example: you want to line up the Addams family so that children come after parents, but spouse and sibling pairs are not separated.

``````# Tsort.sort_strongly_connected_components
["Morticia", ["Gomez"]; "Gomez", ["Morticia"];
"Wednesday", ["Morticia"; "Gomez"; "Pugsley"]; "Pugsley", ["Morticia"; "Gomez"; "Wednesday"];
"Grandmama", []; "Fester", []] ;;

- : string list list =
[["Fester"]; ["Morticia"; "Gomez"]; ["Grandmama"]; ["Wednesday"; "Pugsley"]]

``````

There's also `Tsort.find_strongly_connected_components` if you just want to find what they are. For the data above, it would return `[["Morticia"; "Gomez"]; ["Wednesday"; "Pugsley"]; ["Grandmama"]; ["Fester"]]`.

## Dependencies (3)

1. dune `>= "1.9"`
2. containers `>= "2.7"`
3. ocaml `>= "4.03.0"`

None

## Used by (4)

1. dscheck `>= "0.2.0"`
2. sihl `< "0.2.0" | >= "0.3.0~rc2"`
3. sihl-core
4. soupault `>= "1.12.0" & < "3.1.0"`

## Conflicts

None

Innovation. Community. Security.

##### Ecosystem
Packages Community Events OCaml Planet Jobs
##### Policies
Carbon Footprint Governance Privacy Code of Conduct