Graph traversal in Scala

Question

Graph traversal (DFS and BFS) implementations I know use a mutable set of "visited" vertices. How would you implement them with only immutable data structures?

I saw this question. Now I wonder if there are also other solutions

Answer 1

Here is one way to do it:

def traverse[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A]) : Seq[A] = {
  if(toVisit.isEmpty) {
    Seq.empty
  } else {
    val next = toVisit.head
    val succ = (graph(next) -- visited -- toVisit).toSeq
    // DFS :
    // next +: traverse(graph, succ ++ toVisit.tail, visited + next)
    // BFS :
    next +: traverse(graph, toVisit.tail ++ succ, visited + next)
  }
}

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) =
  traverse(graph, Seq(initial), Set.empty)

The trick is simply to pass around the list of nodes to visit (which would correspond to your stack or queue in an imperative algorithm), and the set of visited states.

If you're worried about the call stack growing with each recursive call, you make it tail-recursive by using an extra argument:

@annotation.tailrec
def traverseTR[A](graph : Map[A,Set[A]], toVisit : Seq[A], visited : Set[A], accumulator : Seq[A]) : Seq[A] = {
  if(toVisit.isEmpty) {
    accumulator
  } else {
    val next = toVisit.head
    val succ = (graph(next) -- visited -- toVisit).toSeq
    // DFS :
    //traverseTR(graph, succ ++ toVisit.tail, visited + next, accumulator :+ next)
    // BFS :
    traverseTR(graph, toVisit.tail ++ succ, visited + next, accumulator :+ next)
  }
}

def traverseFrom[A](graph : Map[A,Set[A]], initial : A) =
  traverseTR(graph, Seq(initial), Set.empty, Seq.empty)

This will give you a version as efficient as if you wrote it using a while loop.

Answer 2

The following code does a few directed graphs traversals. It uses only immutable data structures and is tail recursive, but with some cost:

The List toVisit might contain many duplicates, because it contains all the vertices we plan to visit in the future. In the worst case we might add a vertex to the list for almost every edge in the graph. Hence, the space complexity of the tail recursion is O(|E| + |V|).

For dense graphs, the standard non-tail recursive solution whose space complexity is O(|V|) is more efficient, even-though it does require saving a call stack of length O(|V|).

Since storing the input graph itself requires O(|V| + |E|) space, the above cost might be acceptable. A possible way to improve the space complexity of the above is to replace toVisit with a List[Iterator[Vertex]]. Since Iterators are evaluated lazily this will reduce the space complexity to O(|V|).

object DirectedGraphTraversals {

  type Graph[Vertex] = Map[Vertex, Set[Vertex]]

  def dfs[Vertex](graph: Graph[Vertex], initialVertex: Vertex) =
    dfsRec(DfsNeighbours)(graph, List(initialVertex), Set(), Set(), List())

  def topologicalSort[Vertex](graph: Graph[Vertex]) =
    graphDfsRec(TopologicalSortNeighbours)(graph, graph.keySet, Set(), List())

  def stronglyConnectedComponents[Vertex](graph: Graph[Vertex]) = {
    val exitOrder = graphDfsRec(DfsNeighbours)(graph, graph.keySet, Set(), List())
    val reversedGraph = reverse(graph)

    exitOrder.foldLeft((Set[Vertex](), List(Set[Vertex]()))){
      case ((visitedAcc, connectedComponentsAcc), vertex) =>
        val connectedComponent = dfsRec(DfsNeighbours)(reversedGraph, List(vertex), visitedAcc, visitedAcc, List()).toSet
        (visitedAcc ++ connectedComponent, connectedComponent :: connectedComponentsAcc)
    }._2.filterNot(_.isEmpty)
  }

  def reverse[Vertex](graph: Graph[Vertex]) = {
    val reverseList = for {
      (vertex, neighbours) <- graph.toList
      neighbour <- neighbours
    } yield (neighbour, vertex)

    reverseList.groupBy(_._1).mapValues(_.map(_._2).toSet)
  }

  private sealed trait NeighboursFunc {
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]):Set[Vertex]
  }

  private object DfsNeighbours extends NeighboursFunc {
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) =
      graph.getOrElse(vertex, Set()).filterNot(entered)
  }

  private object TopologicalSortNeighbours extends NeighboursFunc {
    def apply[Vertex](graph: Graph[Vertex], vertex: Vertex, entered: Set[Vertex], exited: Set[Vertex]) = {
      val neighbours = graph.getOrElse(vertex, Set())
      if(neighbours.exists(neighbour => entered(neighbour) && !exited(neighbour)))
        throw new IllegalArgumentException("The graph is not a DAG, it contains cycles: " + graph)
      else
        neighbours.filterNot(entered)
    }
  }

  @tailrec
  private def dfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], toVisit: List[Vertex],
                                                             entered: Set[Vertex], exited: Set[Vertex],
                                                             exitStack: List[Vertex]): List[Vertex] = {
    toVisit match {
      case List() => exitStack
      case hd :: tl =>
        if(exited(hd))
          dfsRec(neighboursFunc)(graph, tl, entered, exited, exitStack)
        else if(entered(hd) && !exited(hd))
          dfsRec(neighboursFunc)(graph, tl, entered, exited + hd, hd :: exitStack)
        else { // not entered yet
          dfsRec(neighboursFunc)(graph, neighboursFunc(graph, hd, entered, exited) ++: toVisit, entered + hd, exited, exitStack)
        }
    }
  }

  @tailrec
  private def graphDfsRec[Vertex](neighboursFunc: NeighboursFunc)(graph: Graph[Vertex], notVisited: Set[Vertex],
                                                                  visited: Set[Vertex], order: List[Vertex]): List[Vertex] = {
    if(notVisited.isEmpty)
      order
    else {
      val orderSuffix = dfsRec(neighboursFunc)(graph, List(notVisited.head), visited, visited, List())
      graphDfsRec(neighboursFunc)(graph, notVisited -- orderSuffix, visited ++ orderSuffix, orderSuffix ::: order)
    }
  }
}

object DirectedGraphTraversalsExamples extends App {
  import DirectedGraphTraversals._

  val graph = Map(
    "B" -> Set("D", "C"),
    "A" -> Set("B", "D"),
    "D" -> Set("E"),
    "E" -> Set("C"))

  //println(dfs(graph, "A"))
  println("dfs A " +  dfs(graph, "A"))
  println("dfs B " +  dfs(graph, "B"))

  println("topologicalSort " +  topologicalSort(graph))
  println("dfs B " +  dfs(graph, "B"))

  println("reverse " + reverse(graph))
  println("stronglyConnectedComponents graph " + stronglyConnectedComponents(graph))

  val graph2 = graph + ("C" -> Set("D"))
  println("stronglyConnectedComponents graph2 " + stronglyConnectedComponents(graph2))
  println("topologicalSort graph2 " + Try(topologicalSort(graph2)))
}

Answer 3

The previous solution has a couple of problems:

It is inefficient: (graph(next) -- visited -- toVisit).toSeq might be linear in the size of the graph.

The DFS version is incorrect, since it does not visit according to the DFS order: For example if you have the following graph:

Map("A" -> Set("B", "D"), "B" -> Set("C", "D"), "C" -> Set(), "D" -> Set("E"), "E" -> Set())

Then if you run DFS starting at A, the legal DFS visiting orders are:

A, B, C, D, E A, B, D, E, C A, D, E, B, C

The above algorithm might visit the vertices in the following illegal order: A, D, B, C, E

Since in the first iteration you add both D and B to the toVisit sequence.

Answer 4

you can traverse like below -

object FindPathsFromANode extends App {

      val startNode = "a"
      val inputNodes = List(Node("a", "x"), Node("a", "b"), Node("b", "c"), Node("c", "d"), Node("b", "y"), Node("b", "z"), Node("d", "a"))

      def findPaths(allNodes: List[Node], newNode: Node, path: List[Node] = Nil, isVisited: List[String] = Nil, allPaths: List[List[Node]] = Nil): List[List[Node]] = {
        if (isVisited.contains(newNode.dest)) {
          allPaths ++ List(path)
        } else {
          val nextNodes = allNodes.filter(_.source == newNode.dest)
          if (nextNodes.isEmpty) {
            allPaths ++ List(path :+ newNode)
          } else if (nextNodes.size > 1) {
            nextNodes.flatMap { node =>
              findPaths(allNodes, node, path :+ newNode, isVisited :+ newNode.source)
            }
          } else {
            findPaths(allNodes, nextNodes.head, path :+ newNode, isVisited :+ newNode.source)
          }
        }
      }

      val startNodes = inputNodes.filter(_.source == startNode)
      startNodes.flatMap(node => findPaths(inputNodes, node)).foreach(println)

    }

Check out the solution at: https://github.com/svsachin13/GraphTraversal-scala