Print Connected Components Scala

Question

Given a file containing adjacent IDs:

i1, i2, i5
i3, i4
i2, i6, i7
i4, i8
i9, i3

I would like to print each of the connected components:

i1, i2, i5, i6, i7
i3, i4, i8, i9

I decided to accomplish this using a BFS on a Map datastructure:

/* Input, can be read from file easily by splitting on ", " */
val lines = List(List("i1", "i2", "i5"),
    List("i3", "i4"),
    List("i2", "i6", "i7"),
    List("i4", "i8"),
    List("i9", "i3"))
/* finds all sequential pairs */
val pairs =  lines.flatMap(x => x.dropRight(1).zip(x.drop(1)))

/* each pair should be symmetric (we are in an undirected graph) */
val pSym = pairs.flatMap(x => List(x, x.swap))

/* create an empty adjacency map: id -> (List of adjacent edges) */
val vertices = lines.flatten.distinct
val defMap = vertices.map(_ -> List[String]()).toMap

/* populate the default map with the actual adjacencies */
val adjMap = pSym.foldLeft{defMap}(
    (acc, x) => acc + (x._1 -> (acc(x._1) :+ x._2))
)

/* BFS algo on map representation of graph */
def mapBFS(adjMap: Map[String, List[String]]): List[List[String]] =
{
    val v = adjMap.keys
    var globalVisits = List[String]()
    def BFS_r(elems: List[String], visited: List[List[String]]): Option[List[List[String]]] =
    {
        val newNeighbors = elems.flatMap(adjMap(_)).filterNot(visited.flatten.contains).distinct
        if (newNeighbors.isEmpty)
            Some(visited)
        else
            BFS_r(newNeighbors, newNeighbors :: visited)
    }
    v.flatMap(x =>{
        if (globalVisits.contains(x))
            None
        else
        {
            val vi: List[String] = BFS_r(List(x), List(List(x))).get.flatten
            globalVisits = globalVisits ++ vi
            Some(vi)
        }
    }).toList
}

mapBFS(adjMap).foreach{println}

This gives me the desired result:

List(i7, i1, i6, i2, i5)
List(i8, i4, i3, i9)

However I feel that this code is not very functional (esp. with the side-effects of updating globalVisits in mapBFS) and I feel like some the data manipulation at the beginning is pretty inefficient. Any thoughts on improvements?

Answer 1

You can always translate loops into a tail-recursive function. Then all you need to do is pass state around as function parameters instead of mutating it in place. IIRC, Scala supports tail-call optimization of direct recursion with the appropriate annotation. That should be good enough in this case.

You actually have done this for BFS_r. You basically just need to do the same thing with the rest of the code.

But first, you're using a lot of Lists that would probably be better off as Sets or Maps. Also, you're keeping track of the nodes that have been visited (globalVisits). I would keep track of the portion of the graph that has not been visited instead -- at least with a tail-recursive solution, since we'll have to get rid of the flatMap.

The first thing is to replace the flatMap with a tail-recursive function:

@tailrec
def loop(unvisited: Map[String, List[String]], accumulator: List[List[String]]): List[List[String]] = {
  if unvisited.empty {
    // We're done => return the accumulator
    return acc
  }
  else{
    // Get the next seed node
    // (Since maps are typically unordered, head is an arbitrary node
    //  that hasn't been visited yet.)
    val seed = unvisited.head

    // Find the component connected to seed
    component = BFS_r(List(seed), List(List(seed)).get.flatten)

    // Iterate, with new unvisited map and component list
    // The new unvisited will have all the nodes in component removed
    // The new accumulator has component added
    return loop(unvisited -- component, component :: accumulator)
}

Then kick it off with:

return loop(adjMap, List())

I haven't done a lot of work with Scala yet, so I can't say this is 100% valid Scala or will work at all. But hopefully the intention is clear. One important to note is that Map and List here are the immutable variants (i.e., from scala.collections.immutable rather than scala.collections.mutable).