# package tsort

Easy to use and user-friendly topological sort

## Sources

2.1.0.tar.gz
`md5=1702f1d89d275f26a021595c2102c39e`
`sha512=cf0a6295eed3ca29dbedb1b32c736b37e98587d5420d2f6443b70ca3c50c8d75c508a245d243a3f28bfe9c250abc3a37d4f461b187d2459670eae4cb088514aa`

## 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"; "Grandmama"];
"Gomez",     ["Morticia"; "Grandmama"];
"Wednesday", ["Morticia"; "Gomez"; "Pugsley"];
"Pugsley",   ["Morticia"; "Gomez"; "Wednesday"];
"Grandmama", [];
"Fester",    []
]
;;

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

``````

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

## Contributing

To run our complete test suite, run `make test-complete` (requires docker).

## Dependencies (2)

1. dune `>= "1.9"`
2. ocaml `>= "4.03.0"`

None

## Used by (4)

1. dkml-install
2. dscheck `>= "0.2.0"`
3. sihl `>= "1.0.0~rc3"`
4. soupault `>= "1.12.0"`

## Conflicts

None

Innovation. Community. Security.

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