Skip to content

Instantly share code, notes, and snippets.

View skp33's full-sized avatar

Kaushal Prajapati skp33

View GitHub Profile
@ThiporKong
ThiporKong / tsort.scala
Last active October 5, 2020 21:35
Topological sorting: simple implementation in pure Scala
def tsort[A](edges: Traversable[(A, A)]): Iterable[A] = {
@tailrec
def tsort(toPreds: Map[A, Set[A]], done: Iterable[A]): Iterable[A] = {
val (noPreds, hasPreds) = toPreds.partition { _._2.isEmpty }
if (noPreds.isEmpty) {
if (hasPreds.isEmpty) done else sys.error(hasPreds.toString)
} else {
val found = noPreds.map { _._1 }
tsort(hasPreds.mapValues { _ -- found }, done ++ found)
}