package tsort

  1. Overview
  2. Docs
Easy to use and user-friendly topological sort

Install

Dune Dependency

Authors

Maintainers

Sources

1.0.0.tar.gz
md5=d7049eadc01cd641ff9e23ec08cc43e1
sha512=b4153c9f266b2b8f468e04e9c3823a9c2a14a92d463825a0b8f1d5777091c425b9327d4f5518fb72ba0b04fc9b54b03fc3a49eeb85e252e9c0cddb06adb7ffb6

Description

Easy to use and user-friendly topological sort.

Example:

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

Published: 21 Nov 2019

README

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"]

Dependencies (3)

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

Dev Dependencies

None

Used by (2)

  1. dscheck >= "0.2.0"
  2. soupault < "1.12.0"

Conflicts

None

OCaml

Innovation. Community. Security.