Skip to content

Instantly share code, notes, and snippets.

@bmarcot

bmarcot/tsort.scala

Created July 30, 2013 11:04
Show Gist options
  • Star 3 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bmarcot/6112036 to your computer and use it in GitHub Desktop.
Save bmarcot/6112036 to your computer and use it in GitHub Desktop.
Download ZIP
Topological sort in Scala.
Raw
tsort.scala
def tsort(gs: List[(Int, List[Int])]): List[Int] = {
gs match {
case g :: gs => {
if (g._2.isEmpty) g._1 :: tsort(gs.diff(List(g)).map(x => (x._1, x._2.diff(List(g._1)))))
else tsort(gs :+ g)
}
case _ => List()
}
}
println(tsort(List((1, List(3, 5)), (2, List(3)), (3, List(4, 5)), (4, List()), (5, List()))))
// List(4, 5, 3, 1, 2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment