Checking whether a graph is connected in an immutable way

Question

I have this function at the moment

  def isConnected(adjacencyListMap: Map[String, Seq[String]]): Boolean = {
    // Simple BFS to check whether each vertex is connected
    val visitedMap = mutable
      .Map[String, Boolean]() ++= adjacencyListMap.keys.map(vertex => vertex -> false).toMap
    val seen = mutable.Stack[String]()
    seen.push(adjacencyListMap.keys.head)

    while (seen.nonEmpty) {
      val v = seen.pop()
      visitedMap.put(v, true)
      val adjacentVertices = adjacencyListMap(v)
      adjacentVertices.foreach(adjVertex => {
        if (!visitedMap(adjVertex)) {
          visitedMap.put(adjVertex, true)
          seen.push(adjVertex)
        }
      })
    }

    // If all vertices are visited then we know all vertices are connected in 1 component
    visitedMap.values.reduce(_ && _)
  }

The function in essence takes in a Map where each vertex is a key and all adjacent vertices to that vertex are values. We basically do a BFS and at the end check whether all vertices were visited, if they were then we know that graph is one component and connected, if not then it is not connected.

How would I go about making this code more immutable (i.e. the mutable seen Stack and mutable visitedMap HashMap)?

Answer 1

completeness

Code posted to Code Review should be complete, correct, and ready for review. You've got everything here except for the import statement needed to allow the mutable collections to compile. Sample input would also be nice but I was able to make do (I think).

layout

The code is organized and well presented but I do find it a bit unusual the way mutable.Map[... has been split. It requires a double-take to read and understand, and it doesn't really help balance the lengths of the two lines. After the ++= would make more sense.

Scala idioms

Replace map(vertex => vertex -> false) with map(_ -> false).

A Map[String, Boolean], i.e. visitedMap, almost exactly imitates the function of a Set[String], where membership is either true or false. You'd have to flip its meaning to notVisited and then remove each element as it gets visited. With that the final result would simply be notVisited.isEmpty.

Single-use variables can be useful to help document the data transformations, but in this case I don't think that val adjacentVertices serves much purpose. The more concise...

adjacencyListMap(v).foreach(adjVertex =>

...is equally as obvious as to what's being done.

You've got an excess (unneeded) pair of braces, { and }, surrounding the if statement.

Instead of reducing all the visitedMap values to a single boolean, all you really want to know is if there are any false values left behind: visitedMap.forall(_._2)

immutable

You're right, a cornerstone of Functional Programming is the use of immutable data. A common way to achieve this is via a recursive method that uses only immutable variables but passes updated data to each iteration.

def isConnected(adjacencyListMap: Map[String, Seq[String]]): Boolean = {
  def loop(from:Set[String], to:Set[String]): Boolean =
    if (from.isEmpty) to.isEmpty
    else (loop _).tupled(to.partition(from.flatMap(adjacencyListMap)))

  val keys = adjacencyListMap.keySet
  loop(Set(keys.head), keys.tail)
}