Dependency Graphs - The Scala Approach

This is the Scala approach of the dependency graph algorithm described in my previous post  Dependency Graphs - A Generic Approach In Java


I am trying to grasp Scala, so don't be too tough on me if you find that my Scala approach is not one of the best.


The graph that was used is the same one used for the Java implementation.

The nodes displayed by the app are the same as in Java: [a, h, b, c, f, e, d, g]


And here is the Scala code:


package org.madeforall.graph


import scala.collection.mutable.HashMap
import scala.collection.mutable.ListBuffer


/**
 * 
 * @author nicolae caralicea
 *
 */
class Graph[T](val evaluatingNodeValueCbk : (T) => Unit) {
private var nodes = HashMap[T, GraphNode[T]]()
private var evaluatedNodes = ListBuffer[GraphNode[T]]()


def addDependency(evalFirstValue : T, evalAfterValue : T) : Unit = {
val firstNode = retrieveOrCreateNodeByValue(evalFirstValue, nodes)
val afterNode = retrieveOrCreateNodeByValue(evalAfterValue, nodes)
firstNode.goingOutNodes += afterNode
afterNode.comingInNodes += firstNode
if(! nodes.contains(evalFirstValue)) nodes.put(evalFirstValue, firstNode)
if(! nodes.contains(evalAfterValue)) nodes.put(evalAfterValue, afterNode)
}


private def retrieveOrCreateNodeByValue(value : T, nodes : HashMap[T, GraphNode[T]]) : GraphNode[T] = {
nodes.get(value) match {
case Some(node) => node
case None => new GraphNode[T](value)
}
}

private def getOrphanNodes() : ListBuffer[GraphNode[T]] = {
nodes.foldLeft(ListBuffer[GraphNode[T]]()) {
(list, kv) =>  if(kv._2.comingInNodes.isEmpty) list += kv._2 else list
}
}

def generateDependencies() : Unit ={
val orphanNodes = getOrphanNodes()
var nextNodesToDisplay = ListBuffer[GraphNode[T]]()
orphanNodes.foreach(node => {
evaluatingNodeValueCbk(node.value)
evaluatedNodes += node
nextNodesToDisplay ++= node.goingOutNodes 
})
if(! nextNodesToDisplay.isEmpty) generateDependencies(nextNodesToDisplay)
}


private def generateDependencies(nodes : ListBuffer[GraphNode[T]]) : Unit = {
var nextNodesToDisplay = ListBuffer[GraphNode[T]]()
nodes.foreach((node) => {
if(! evaluatedNodes.contains(node)) {
if(areAlreadyEvaluated(node.comingInNodes)) {
evaluatingNodeValueCbk(node.value)
evaluatedNodes += node
nextNodesToDisplay ++= node.goingOutNodes
} else {
nextNodesToDisplay += node
}
}
})
if(! nextNodesToDisplay.isEmpty) generateDependencies(nextNodesToDisplay)
}
private def areAlreadyEvaluated(nodes : ListBuffer[GraphNode[T]]) : Boolean = {
! nodes.exists(node => ! evaluatedNodes.contains(node))
}
}


object Tests {
  def main(args: Array[String]): Unit = {  
 val graphInt = new Graph[Int](item => print(item + ", "))
 graphInt.addDependency(1,2)
 graphInt.addDependency(1,3)
 graphInt.addDependency(3,4)
 graphInt.addDependency(3,5)
 graphInt.addDependency(5,8)
 graphInt.addDependency(2,7)
 graphInt.addDependency(2,9)
 graphInt.addDependency(2,8)
 graphInt.addDependency(9,10)
 print("\n[Int]:")
 graphInt.generateDependencies()

 val graphString = new Graph[String](item => print(item + ", "))
 graphString.addDependency("a", "b")
 graphString.addDependency("a", "c")
 graphString.addDependency("a", "f")
 graphString.addDependency("c", "d")
 graphString.addDependency("d", "g")
 graphString.addDependency("f", "d")
 graphString.addDependency("h", "e")
 print("\n[String]:")
 graphString.generateDependencies()      
  }
} 


package org.madeforall.graph


import scala.collection.mutable.ListBuffer


/**
 * 
 * @author nicolae caralicea
 *
 */
class GraphNode[T](val value : T) {
var comingInNodes = ListBuffer[GraphNode[T]]()
var goingOutNodes = ListBuffer[GraphNode[T]]()
}


Dependency Graphs - The Scala Approach by nicolae caralicea is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.
Based on a work at nicolaecaralicea.blogspot.com.