How to implement a DFS with immutable data types

Question

I'm trying to figure out a neat way of traversing a graph Scala-style, preferably with vals and immutable data types.

Given the following graph,

val graph = Map(0 -> Set(1),
                1 -> Set(2),
                2 -> Set(0, 3, 4),
                3 -> Set(),
                4 -> Set(3))

I'd like the output to be the depth first traversal starting in a given node. Starting in 1 for instance, should yield for instance 1 2 3 0 4.

I can't seem to figure out a nice way of doing this without mutable collections or vars. Any help would be appreciated.

Answer 1

Tail Recursive solution:

  def traverse(graph: Map[Int, Set[Int]], start: Int): List[Int] = {
    def childrenNotVisited(parent: Int, visited: List[Int]) =
      graph(parent) filter (x => !visited.contains(x))

    @annotation.tailrec
    def loop(stack: Set[Int], visited: List[Int]): List[Int] = {
      if (stack isEmpty) visited
      else loop(childrenNotVisited(stack.head, visited) ++ stack.tail, 
        stack.head :: visited)
    }
    loop(Set(start), Nil) reverse
  }

Answer 2

Here is recursive solution (hope I understood your requirements correctly):

def traverse(graph: Map[Int, Set[Int]], node: Int, visited: Set[Int] = Set()): List[Int] = 
    List(node) ++ (graph(node) -- visited flatMap(traverse(graph, _, visited + node)))

traverse(graph, 1)

Also please note, that this function is NOT tail recursive.

Answer 3

This is one variant I guess:

graph.foldLeft((List[Int](), 1)){
  (s, e) => if (e._2.size == 0) (0 :: s._1, s._2) else (s._2 :: s._1, (s._2 + 1))
}._1.reverse

Updated: This is an expanded version. Here I fold left over the elements of the map starting out with a tuple of an empty list and number 1. For each element I check the size of the graph and create a new tuple accordingly. The resulting list come out in reverse order.

val init = (List[Int](), 1)
val (result, _) = graph.foldLeft(init) {
  (s, elem) => 
    val (stack, count) = s
    if (elem._2.size == 0) 
      (0 :: stack, count) 
    else 
      (count :: stack, count + 1)
}
result.reverse