Another Scala code snippet for linearising a graph

This algorithm is more or less related to Topological sorting. It can be useful for computing DAG in parallel.....

  type ListMap = Map[Vertex, List[Vertex]]
  class Vertex {
    var children: List[Vertex] = List()
    def isLeaf = children.isEmpty
  }
  class Graph {
    def roots: List[Vertex] = List()
  }
  
  def lin(g: Graph): ListMap = {
    def dfs(n: Vertex):List[Vertex] = if (n.isLeaf) List() else (for(c <- n.children) yield c :: dfs(c)).flatten
    def shrink(dfsl: List[Vertex]): List[Vertex] = {
      def shrink(il: List[Vertex], ol: List[Vertex]): List[Vertex] =
        if (il.isEmpty) ol
        else if (!ol.contains(il.head)) shrink(il.tail, (ol ++ List(il.head)))
        else shrink(il.tail, ol diff List(il.head)) ::: List(il.head)
      if (dfsl.isEmpty) List() else shrink(dfsl, List())
   }
   (for(r <- g.roots) yield (r, shrink(dfs(r)))).toMap
  }