Scala: immutable Map is changing its values

Question

I am writing a code to determine a k-colorable Graph. I am using immutable Maps to determine vertices colors on backtracking.

On the second interaction of a flatMap loop, my Map lost an element. I couldn't be able to write a more concise example that would present the same bug, then here it is my entire code:

import scala.collection.immutable
import scala.collection.mutable

class GraphUndirected[Vertex](vertices: Set[Vertex], edges: Set[(Vertex, Vertex)]) {
  private val adjacencyList: Map[Vertex, Set[Vertex]] =
    (
      edges.flatMap{ case (a, b) => {Seq( (a, Set(b)), (b, Set(a)))}}
        ++ vertices.map((_, Set()))
      )
      .groupBy(_._1)
      .mapValues(
        _.map(_._2)
          .reduce(_ ++ _)
          .toSet
      )

  override def toString(): String = adjacencyList.toString

  def kColorable[C](colors: Set[C]): Option[Map[Vertex, C]] = {
    vertices.toSeq.view.flatMap( v => {
      val colorsMap = immutable.Map[Vertex,C]()
      kColorable[C](colors, v, colorsMap)
    }).headOption
  }

  def kColorable[C](colors: Set[C], v: Vertex, colorMap: Map[Vertex, C]): Option[Map[Vertex, C]] = {
    println(v, colorMap)

    colors.toSeq.view.flatMap( c => {
      if (kColorableIsSafe[C](c, v, colorMap)) {
        val newColorMap = colorMap + (v -> c)
        println("\tnewColorMap", newColorMap)

        if (newColorMap.size == vertices.size) {
          Some(newColorMap)
        } else {
          adjacencyList(v).toSeq.view.flatMap( u => {
            println("\t\tnewColorMap", newColorMap)

            if (newColorMap.contains(u)) {
              None
            } else {
              kColorable[C](colors, u, newColorMap)
            }
          }).headOption
        }
      } else {
        None
      }
    }).headOption
  }

  def kColorableIsSafe[C](c: C, v: Vertex, colorMap: Map[Vertex, C]): Boolean = {
    adjacencyList(v).forall( u => {
      (!colorMap.contains(u)) ||
        (colorMap(u) != c)
    })
  }
}

val myGraph1 = new GraphUndirected[Int](
  Set(1,2,3,4,5,6,7,8,9),
  Set(
    (1,2),
    (3,2), (3,4),
    (5,7), (5,9),
    (6,4),
    (8,2), (8,9)
  )
)
println(myGraph1.kColorable[String](Set("BLACK", "WHITE")))

Running this code will produce:

(5,Map())
(       newColorMap,Map(5 -> BLACK))
(               newColorMap,Map(5 -> BLACK))
(7,Map(5 -> BLACK))
(       newColorMap,Map(5 -> BLACK, 7 -> WHITE))
(               newColorMap,Map(5 -> BLACK, 7 -> WHITE))
(               newColorMap,Map(5 -> BLACK))
(9,Map(5 -> BLACK))

It does not make sense for me. In the first interaction it prints newColorMap,Map(5 -> BLACK, 7 -> WHITE), but in the second the "7->WHITE" is gone newColorMap,Map(5 -> BLACK).

newColorMap wasn't supposed to be immutable, not changing its value?

---

My Scala version:

$ scala -version
Scala code runner version 2.12.2 -- Copyright 2002-2017, LAMP/EPFL and Lightbend, Inc.

Answer 1

Your code seems bug-free to me. It returns the expected output. What is deceptive is the way you have chosen to output the internal state of your program as you step through it.

To understand what's going on, try running this version of the same program. Just copy and paste the code into Kcolor.scala, drop it in its folder and type in

scalac Kcolor.scala
scala Kcolor

Here are the contents of Kcolor.scala

import scala.collection.immutable

object Kcolor extends App {

  val myGraph1 = new GraphUndirected[Int](
    Set(5,7,9),
    Set((5,7), (5,9))
  )
  println(myGraph1.kColorable[String](Set("BLACK", "WHITE")))

}

class GraphUndirected[Vertex](vertices: Set[Vertex], edges: Set[(Vertex, Vertex)]) {
  val adjacencyList: Map[Vertex, Set[Vertex]] =
    (
      edges.flatMap{ case (a, b) => {Seq( (a, Set(b)), (b, Set(a)))}}
        ++ vertices.map((_, Set()))
      )
      .groupBy(_._1)
      .mapValues(
        _.map(_._2)
          .reduce(_ ++ _)
          .toSet
      )

  override def toString(): String = adjacencyList.toString

  def kColorable[C](colors: Set[C]): Option[Map[Vertex, C]] = {
    vertices.flatMap( v => {
      val colorsMap = immutable.Map[Vertex,C]()
      kColorable[C](colors, v, colorsMap)
    }).headOption
  }

  def kColorable[C](colors: Set[C], v: Vertex, colorMap: Map[Vertex, C]): Option[Map[Vertex, C]] = {
    println(v, colorMap)

    val res = colors.flatMap( c => {
      if (kColorableIsSafe[C](c, v, colorMap)) {
        val newColorMap = colorMap + (v -> c)
        println("\tnewColorMap", v, c, newColorMap)

        if (newColorMap.size == vertices.size) {
          Some(newColorMap)
        } else {
          val res1 = adjacencyList(v).flatMap( u => {
            println("\t\tnewColorMap", u, newColorMap)

            if (newColorMap.contains(u)) {
              None
            } else {
              kColorable[C](colors, u, newColorMap)
            }
          })
          println(res1)
          res1.headOption
        }
      } else {
        None
      }
    }).headOption
    println("end")
    res
  }

  def kColorableIsSafe[C](c: C, v: Vertex, colorMap: Map[Vertex, C]): Boolean = {
    adjacencyList(v).forall( u => {
      (!colorMap.contains(u)) ||
        (colorMap(u) != c)
    })
  }
}

I have included the first few lines of the output:

(5,Map())
(       newColorMap,5,BLACK,Map(5 -> BLACK))
(               newColorMap,7,Map(5 -> BLACK))
(7,Map(5 -> BLACK))
(       newColorMap,7,WHITE,Map(5 -> BLACK, 7 -> WHITE))
(               newColorMap,5,Map(5 -> BLACK, 7 -> WHITE))
Set()
end
(               newColorMap,9,Map(5 -> BLACK))
(9,Map(5 -> BLACK))
(       newColorMap,9,WHITE,Map(5 -> BLACK, 9 -> WHITE))
(               newColorMap,5,Map(5 -> BLACK, 9 -> WHITE))
Set()
end

What the program is doing is that it's reaching the end of the flatMap without being able to create a colorized map, and it is outputting None. So between the line

(               newColorMap,5,Map(5 -> BLACK, 7 -> WHITE))

and

(               newColorMap,9,Map(5 -> BLACK))

it is reaching the end of the current flatMap and jumping back to the next iteration of the outer loop.

Your program is very interesting. I had fun thinking about it. Thanks for sharing.