dmbaturin / ocaml-tsort

Easy to use and user-friendly topological sort module for OCaml

ocaml-tsort

ocaml-tsort is a library for sorting graphs in topological order. Its UI/UX is inspired by the classic UNIX tsort(1).

• Uses Kahn's algorithm.
• Easy to use, but not very fast.
• Provides friendly error reporting (e.g., if there's a cycle, tells you what the offending nodes are).

The input type is (('a * 'a list) list). Essentially, a list of "tasks" mapped to 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 input, 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: suppose 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).

ocaml-tsort's Issues

Clarify handling of bad input

Consider the following dependencies: 1 -> 2, 3 and 2 -> 1. A natural but inappropriate way to specify it is [(1, [2]); (2, [1]); (1, [3])], in other words, a list where each pair expresses some possibly incomplete dependency. The current behaviour of Tsort on these is not consistent: sometimes it rejects the input with an assert false and sometimes it computes the meaningful output.

utop # let l = [(1, [3]); (2, [1]); (1, [2])];;
val l : (int * int list) list = [(1, [3]); (2, [1]); (1, [2])]
──────────────
utop # Tsort.sort_strongly_connected_components l;;
- : int list list = [[3]; [2; 1]]
──────────────
utop # let l = [(1, [2]); (2, [1]); (1, [3])];;
val l : (int * int list) list = [(1, [2]); (2, [1]); (1, [3])]
──────────────
utop # Tsort.sort_strongly_connected_components l;;
Exception: Assert_failure ("src/lib/tsort.ml", 287, 22).

It would be nice to

• Have a consistent behaviour: always reject (with a readable error message), or always accept these inputs
• State how such inputs are treated in the documentation.

Add CI before the next release

I'd like to set up CircleCI before making a release. It's free for open-source projects and would give us a guarantee that a release will work for a desired range of OCaml versions.

It requires the github project owner to:

1. Create a CircleCI account
2. Add the project from the CircleCI dashboard
3. Add me as a contributor on the CircleCI project so I can set things up

The setup will consist in adding a .circleci folder to the github project, which CircleCI will use to build the project with every commit and notify us if something fails. See https://github.com/mjambon/dune-deps/tree/master/.circleci for an example.