Cycle detection

What if we introduce a cycle? For example, refer to the cycle shown here:

Cycle detection

If you invoke the topsort method with this graph as an argument, it will never be completed:

scala> topsort(("dinner", "movie") :: grwork) 
java.lang.StackOverflowError 
...  

The fix is to remember that x is already seen, going to precede, so processing x again is a cycle. We just abort the execution in this case:

scala> def topsortWithCycle(g: List[(String, String)]) = { | def sort(nodes: List[String], path: List[String], visited: List[String]): | List[String] = nodes match { | case Nil => visited | case x :: xs if path.contains(x) => | throw new RuntimeException("Cycle ...

Get Learning Functional Data Structures and Algorithms now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.