12
\$\begingroup\$

I started coding in Scala some time ago, and also learning some fundamental algorithms in CS.

Here's a terribly slow implementation of Kosaraju algorithm to find strongly connected components in a graph.

I'm looking for three things:

  • Learning how to use Scala data structures
  • Learning how to implement this algorithm in \$O(m+n)\$ time
  • Learning more about Scala's best practices, and how to implement them.

The input style is the following. The first number is a vertex, the second a directed connection in the graph:

1 2
2 3
3 1
3 4
5 4
6 4
8 6
6 7
7 8

Original implementation:

import scala.io.Source                                                                                                                                                                                             
import util.Random.nextInt
import scala.collection.{mutable, immutable}
import scala.runtime.ScalaRunTime._
import scala.util.control.Breaks._

object Kosaraju {
  val usage = """
    Usage: scala Kosaraju.scala [filename]
  """

  var t: Int = 0
  var s: Int = 0
  var scc: Int = 0
  var finish_list: mutable.HashMap[Int, Int] = mutable.HashMap[Int,Int]()
  var explored_list: List[Int] = List()
  var leader: mutable.HashMap[Int,mutable.Buffer[Int]] = mutable.HashMap[Int,mutable.Buffer[Int]]()
  var scc_map: mutable.HashMap[Int,mutable.Buffer[Int]] = mutable.HashMap[Int,mutable.Buffer[Int]]()

  def main (args: Array[String]) {
    if (args.length != 1) {
      println(usage)
      return
    }
    val filename = args.toList(0)
    val edges: mutable.Buffer[Array[Int]] = 
      Source.fromFile(filename).getLines().map(_.split(" ").map(_.toInt)).toBuffer

    //edges.foreach(e => println(e(0).toString + ' ' + e(1).toString))

    var double_adj_list: mutable.HashMap[Int, mutable.Buffer[mutable.Buffer[Int]]] =
      mutable.HashMap[Int,mutable.Buffer[mutable.Buffer[Int]]]()

    println("Building double adjacency list....")

    edges.foreach { e =>
      if (! double_adj_list.contains(e(0))) {
        double_adj_list +=
          (e(0) -> mutable.Buffer[mutable.Buffer[Int]](mutable.Buffer[Int](e(1)),
                                                       mutable.Buffer[Int]()))
      } else {
        double_adj_list(e(0))(0).append(e(1))
      }

      if (! double_adj_list.contains(e(1))) {
        double_adj_list +=
          (e(1) -> mutable.Buffer[mutable.Buffer[Int]](mutable.Buffer[Int](),
                                                       mutable.Buffer[Int](e(0))))
      } else {
        double_adj_list(e(1))(1).append(e(0))
      }
    }
    println("...Done")

    println("First round of DFS....")

    (1 to double_adj_list.keys.size).reverse.foreach ( e =>
      if (! explored_list.contains(e)) {
        s = e
        leader += (s -> mutable.Buffer[Int](s)) 
        DFS(double_adj_list, e, 1, 0)
      })

    println("...Done")
    println("Second round of DFS....")

    explored_list = List()

    (1 to double_adj_list.keys.size).reverse.foreach ( e =>
      if (! explored_list.contains(finish_list(e))) {
        s = finish_list(e)
        scc += 1
        scc_map += (s -> mutable.Buffer[Int](s))
        DFS(double_adj_list, s, 0, 1)
      })

    println("...Done")

    scc_map.keys.foreach ( k =>
      println(scc_map(k).length))
  }

  def DFS(double_adj_list: mutable.HashMap[Int, mutable.Buffer[mutable.Buffer[Int]]],
          node: Int,
          dir: Int,
          count: Int): Any = {
    explored_list = explored_list :+ node
    if (count == 0 && ! leader(s).contains(node)) {
      leader(s) = leader(s) :+ node
    }

    double_adj_list(node)(dir).foreach ( l =>
      if (! explored_list.contains(l)) {
        if (count == 1) {
          scc_map(s) += l
        }
        DFS(double_adj_list, l, dir, count)
      })

    if (count == 0) {
      t += 1
      finish_list += (t -> node)
    }
  }
}
\$\endgroup\$
13
\$\begingroup\$

The first thing that I see is a fundamental issue that would be a problem regardless of the programming language used - long procedures.

The folks who study the human aspects of software development have strong evidence suggesting that readability is critical to making code easier to understand and therefore maintain. One of the critical factors in readability is length - longer procedures are harder to read/understand.

One good way to improve readability is to extract out parts of a long method that do one specific thing.

Take, for example, these lines from the beginning of the main function:

if (args.length != 1) {
  println(usage)
  return
}
val filename = args.toList(0)
val edges: mutable.Buffer[Array[Int]] = 
  Source.fromFile(filename).getLines().map(_.split(" ").map(_.toInt)).toBuffer

These lines load the edges from a file. Yes, they also validate the parameter list as part of that, but mainly they load the edges. So you could extract that into a function that looked something like this.

def loadEdges(args: Array[String]): Option[mutable.Buffer[Array[Int]]] = {
  if (args.length == 1) { 
      val filename = args(0)
      Source.fromFile(filename).getLines().map(_.split(" ").map(_.toInt)).toBuffer
  } else {
      println(usage)
      None
  }
}

As a learning exercise, you should go through the rest of the code looking for other blocks that do one thing.

So in main, the beginning might look something like this:

def main (args: Array[String]) {
  val edges = loadEdges(args) match {
    case None => return
    case Some(e) => e
  }

Someone reading this can see that the first thing that happens is that the edges are loaded. It says so right there. Much clearer.

I did make edges a val rather than a var, because it is never updated, and I left off the type because it's kind of long and ugly and I'm not entirely convinced that putting it in actually says anything useful. Some organizations have coding standards that require every variable to be fully defined so Your Mileage May Vary.

You could also use a for comprehension, especially if main gets significantly shorter. That would look something like this:

def main(args: Array[String]) {
  for (edges <- loadEdges(args)) {
    // the rest of the algorithm goes here
    // edges is a "variable" defined only within the scope of the "loop"
  }
}
\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your answer. I updated my question with the edge being loaded in a method, and the build of the adjacency list in a method as well. As I am doing different things each time I call DFS on the list, I thought it was ok to leave that work in main, but that might be wrong. \$\endgroup\$ – Bacon Aug 22 '15 at 23:13
  • \$\begingroup\$ @Bacon, don't update your original code. If you think you have some improvements, based on answers/comments, post your own answer saying "Based on feedback, I've tried these improvements". People can then comment on that. \$\endgroup\$ – itsbruce Aug 23 '15 at 15:59
  • \$\begingroup\$ I left the original code in the question. is that really better to spawn a new answer? I don't know yet the best practice for codereview. \$\endgroup\$ – Bacon Aug 23 '15 at 16:35
  • 1
    \$\begingroup\$ @Bacon The accepted answer to this question on the meta site gives extensive advice. Better to add an answer showing the improvements you have tested and explaining how they improve it. If you keep editing the original question as people add new suggestions, some answers will become partially/entirely wrong or irrelevant. Also, others will not be able to suggest alternative improvements to the original. \$\endgroup\$ – itsbruce Aug 24 '15 at 0:30
  • \$\begingroup\$ I'll do that then \$\endgroup\$ – Bacon Aug 24 '15 at 0:40
3
+50
\$\begingroup\$

The obvious place to look for the performance issue is explored_list. The only operations you perform on explored_list are to add values and to test whether it contains values, but List is the worst* data structure available for testing whether it contains a given value. The minimal change to fix this problem would be to instead use a HashSet.

However, HashMaps and HashSets are fairly general data structures, and not all of your code assumes that level of generality. In particular:

  1. The types of the various lists and maps assume that the vertices of the graph will be Ints.
  2. (1 to double_adj_list.keys.size) assumes that the vertices of the graph are consecutive integers.

Given those assumptions, there's a strong case to be made for replacing the maps and sets with arrays. (Or, alternatively, for fully generalising the connected components code into a generic class and making the test wrapper instantiate it as Kosaraju[Int]).

* Modulo deliberate construction of a data structure which takes worse than linear time to test membership.

\$\endgroup\$
  • \$\begingroup\$ For the explored_list, can you confirm that the running times specified here: stackoverflow.com/a/2713483/296549 are indeed true? In my case I have 2n lookups and inserts, where n is the number of edges. So I guess that if we take the running times, an Array would be in the worst case O(1)*2n + O(n)*2n (which is O(n^2) if I'm right), and a List would be O(n)*2n*2 (which is also O(n^2) but with much higher constants) \$\endgroup\$ – Bacon Sep 2 '15 at 13:10
  • \$\begingroup\$ As for replacing maps with arrays, could that be done by having arrays of tuples? I somehow still need a mapping between the leaders, for example, and it's related edges. Or would that be better to have an Array with only the related edges as values, indexed by the leader's edge number? \$\endgroup\$ – Bacon Sep 2 '15 at 13:11
  • \$\begingroup\$ If explored_list is implemented as an array of Booleans then you would get O(n) instead of the current O(n^2). The replacing of maps with arrays would be a case of changing HashMap[Int, T] to Array[T]. Maps are basically a generalisation of arrays which don't require the keys to be a fixed range of integers starting at 0: that's why in e.g. Perl they're called associative arrays. \$\endgroup\$ – Peter Taylor Sep 2 '15 at 13:32
1
\$\begingroup\$

Updated implementation with Donald's feedbacks. The code is made more readable by putting the file parsing and adjacency list build in dedicated methods.

import scala.io.Source                                                                                                                                                                                             
import util.Random.nextInt
import scala.collection.{mutable, immutable}
import scala.runtime.ScalaRunTime._
import scala.util.control.Breaks._

object Kosaraju {
  val usage = """
    Usage: scala Kosaraju.scala [filename]
  """

  var t: Int = 0
  var s: Int = 0
  var scc: Int = 0
  var finish_list: mutable.HashMap[Int, Int] = mutable.HashMap[Int,Int]()
  var explored_list: List[Int] = List()
  var leader: mutable.HashMap[Int,mutable.Buffer[Int]] = mutable.HashMap[Int,mutable.Buffer[Int]]()
  var scc_map: mutable.HashMap[Int,mutable.Buffer[Int]] = mutable.HashMap[Int,mutable.Buffer[Int]]()

  def main (args: Array[String]) {
    val edges = loadEdges(args) match {
      case None    => return 
      case Some(e) => e
    }

    println("First round of DFS....")

    val double_adj_list = buildDoubleAdjacencyList(edges)

    (1 to double_adj_list.keys.size).reverse.foreach ( e =>
      if (! explored_list.contains(e)) {
        s = e
        leader += (s -> mutable.Buffer[Int](s)) 
        DFS(double_adj_list, e, 1, 0)
      })

    println("...Done")
    println("Second round of DFS....")

    explored_list = List()

    (1 to double_adj_list.keys.size).reverse.foreach ( e =>
      if (! explored_list.contains(finish_list(e))) {
        s = finish_list(e)
        scc += 1
        scc_map += (s -> mutable.Buffer[Int](s))
        DFS(double_adj_list, s, 0, 1)
      })

    println("...Done")
    scc_map.keys.foreach ( k =>
      println(scc_map(k).length))
  }

  def DFS(double_adj_list: mutable.HashMap[Int, mutable.Buffer[mutable.Buffer[Int]]],
          node: Int,
          dir: Int,
          count: Int): Any = {
    explored_list = explored_list :+ node
    if (count == 0 && ! leader(s).contains(node)) {
      leader(s) = leader(s) :+ node
    }

    double_adj_list(node)(dir).foreach ( l =>
      if (! explored_list.contains(l)) {
        if (count == 1) {
          scc_map(s) += l
        }
        DFS(double_adj_list, l, dir, count)
      })

    if (count == 0) {
      t += 1
      finish_list += (t -> node)
    }
  }

  def loadEdges(args: Array[String]): Option[mutable.Buffer[Array[Int]]] = {
    if (args.length == 1) {
      val filename = args.toList(0)
      Some(Source.fromFile(filename).getLines().map(_.split(" ").map(_.toInt)).toBuffer)
    } else {
      println(usage)
      None
    }
  }

  def buildDoubleAdjacencyList(edges: mutable.Buffer[Array[Int]]):
    mutable.HashMap[Int, mutable.Buffer[mutable.Buffer[Int]]] = {
      println("Building double adjacency list....")

     var double_adj_list: mutable.HashMap[Int, mutable.Buffer[mutable.Buffer[Int]]] =
       mutable.HashMap[Int,mutable.Buffer[mutable.Buffer[Int]]]()

      edges.foreach { e =>
        if (! double_adj_list.contains(e(0))) {
          double_adj_list +=
            e(0) -> mutable.Buffer[mutable.Buffer[Int]](mutable.Buffer[Int](e(1)),
                                                        mutable.Buffer[Int]())
        } else {
          double_adj_list(e(0))(0).append(e(1))
        }

        if (! double_adj_list.contains(e(1))) {
          double_adj_list +=
            (e(1) -> mutable.Buffer[mutable.Buffer[Int]](mutable.Buffer[Int](),
                                                         mutable.Buffer[Int](e(0))))
        } else {
          double_adj_list(e(1))(1).append(e(0))
        }
      }

      println("...Done")
      double_adj_list
  }
}  
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.