Skip to content
Easy to use and user-friendly topological sort module for OCaml
OCaml
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
src
.gitignore
LICENSE
README.md
dune
dune-project
tsort.opam

README.md

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.

The output is a tri-state sum type. This is the entire module interface:

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

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

Dependencies on nodes that don't exist in the set of keys cause the ErrorNonexistent error, while cycles produce ErrorCycle. 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.ErrorNonexistent ["building permit"]

# Tsort.sort [("foundation", ["roof"]); ("walls", ["foundation"]); ("roof", ["walls"])] ;;
- : string Tsort.sort_result = Tsort.ErrorCycle ["roof"; "foundation"; "walls"]
You can’t perform that action at this time.