Toposort for Kotlin

Topological sorting algorithms implemented in Kotlin.

This library contains the following top-level functions:

• fun <T> toposortKahn(graph: Map<T, List<T>>)

  Returns topologically sorted elements of a graph using Kahn’s algorithm. Note that graph contains the adjacency list for each vertex. One can also interpret graph as a Hasse diagram of partial order.

• fun <T> toposortLayers(deps: Map<T, List<T>>)

  Performs a topological sort by returning elements by layers. Note that deps represents the dependencies of each element. The order of produced elements is "reversed" with respect to toposortKahn function. One can also interpret deps as a Hasse diagram with reversed edges — the returned layers correspond to anti-chains in partial order.