Scala DSL for parsing and evaluating of arithmetic expressions

In this post I want to show you a simple way to parse and evaluate arithmetic expressions by using Scala Parser Combinators.

So, I will try to do the followings:

1. create a parser able to recognize complex arithmetic expressions
2. parse arithmetic expression and generate the parse result as a list of strings that corresponds to the postfix notation of the initial expression
3. evaluate the above postfix notation list to generate the value of the arithmetic expression

To better understand the code I would also recommend you to read the following links if you are not that familiar with Scala parser combinators and the postfix notation:

Chapter 31 of Programming in Scala, First Edition Combinator Parsing by Martin Odersky, Lex Spoon, and Bill Venners December 10, 2008

Reverse Polish notation

And here is the code:

import scala.util.parsing.combinator._

/**
* @author Nicolae Caralicea
* @version 1.0, 04/01/2013
*/

class Arithm extends JavaTokenParsers {
  def expr: Parser[List[String]] = term ~ rep(addTerm | minusTerm) ^^
    { case termValue ~ repValue => termValue ::: repValue.flatten }

  def addTerm: Parser[List[String]] = "+" ~ term ^^
    { case "+" ~ termValue => termValue ::: List("+") }

  def minusTerm: Parser[List[String]] = "-" ~ term ^^
    { case "-" ~ termValue => termValue ::: List("-") }

  def term: Parser[List[String]] = factor ~ rep(multiplyFactor | divideFactor) ^^
    {
      case factorValue1 ~ repfactor => factorValue1 ::: repfactor.flatten
    }

  def multiplyFactor: Parser[List[String]] = "*" ~ factor ^^
    { case "*" ~ factorValue => factorValue ::: List("*") }

  def divideFactor: Parser[List[String]] = "/" ~ factor ^^
    { case "/" ~ factorValue => factorValue ::: List("/") }

  def factor: Parser[List[String]] = floatingPointConstant | parantExpr

  def floatingPointConstant: Parser[List[String]] = floatingPointNumber ^^
    {
      case value => List[String](value)
    }

  def parantExpr: Parser[List[String]] = "(" ~ expr ~ ")" ^^
    {
      case "(" ~ exprValue ~ ")" => exprValue
    }

  def evaluateExpr(expression: String): Double = {
    val parseRes = parseAll(expr, expression)
    if (parseRes.successful) evaluatePostfix(parseRes.get)
    else throw new RuntimeException(parseRes.toString())
  }

  private def evaluatePostfix(postfixExpressionList: List[String]): Double = {
    import scala.collection.immutable.Stack

    def multiply(a: Double, b: Double) = a * b
    def divide(a: Double, b: Double) = a / b
    def add(a: Double, b: Double) = a + b
    def subtract(a: Double, b: Double) = a - b

    def executeOpOnStack(stack: Stack[Any], operation: (Double, Double) => Double): (Stack[Any], Double) = {
      val el1 = stack.top
      val updatedStack1 = stack.pop
      val el2 = updatedStack1.top
      val updatedStack2 = updatedStack1.pop
      val value = operation(el2.toString.toDouble, el1.toString.toDouble)
      (updatedStack2.push(operation(el2.toString.toDouble, el1.toString.toDouble)), value)
    }
    if (postfixExpressionList.length == 1) toDouble(postfixExpressionList.head)
    else {
      val initial: (Stack[Any], Double) = (Stack(), null.asInstanceOf[Double])
      val res = postfixExpressionList.foldLeft(initial)((computed, item) =>
        item match {
          case "*" => executeOpOnStack(computed._1, multiply)
          case "/" => executeOpOnStack(computed._1, divide)
          case "+" => executeOpOnStack(computed._1, add)
          case "-" => executeOpOnStack(computed._1, subtract)
          case other => (computed._1.push(other), computed._2)
        })
      res._2
    }
}

object TestArithmDSL {
  def main(args: Array[String]): Unit = {
    val arithm = new Arithm
    val actual = arithm.evaluateExpr("(12 + 4 * 6) * ((2 + 3 * ( 4 + 2 ) ) * ( 5 + 12 ))")
    val expected: Double = (12 + 4 * 6) * ((2 + 3 * ( 4 + 2 ) ) * ( 5 + 12 ))
    assert(actual == expected)
  }
}

Graphs - Finding the Minimum Spanning Tree - A Generic Scala implementation of Prim's algorithm

In this post I am trying to provide you a basic implementation of Prim's algorithm in Scala.

I also tried to make it more generic.

So, here is how I defined the Node, Edge, and UndirectedGraph (just a part of it) classes.

case class Node(name: String)
case class Edge[T <% Ordered[T]](xNodeName: String, yNodeName: String, cost: T)

case class UndirectedGraph[T <% Ordered[T]](nodes: List[Node], edgetList: List[Edge[T]])

Here is the declaration of the  function that provides the sought result:

def computeMinimumSpanningTreeUsingPrim(): UndirectedGraph[T]

 I am also using this opportunity to introduce you to "Views and view bounds".
This is another great Scala feature. I'm not going to dive into more details about it.

So, as long as there is a "view" from T to Ordered[T], this algorithm is supposed to work properly.

Note that, "T <% Ordered[T]" is one of the most used views in Scala.


On Wikipedia you can also find a good explanation if the Prim's algorithm, so I wont go into more details.

Here is the link:

http://en.wikipedia.org/wiki/Prim%27s_algorithm



And here is the code:

package org.madeforall.graph.mst.prim

/**

 * @author Nicolae Caralicea

 * @version 1.0, 26/01/2013

 */

case class Node(name: String)
case class Edge[T <% Ordered[T]](xNodeName: String, yNodeName: String, cost: T)

case class UndirectedGraph[T <% Ordered[T]](nodes: List[Node], edgetList: List[Edge[T]]) {
  case class NodesEdge[T <% Ordered[T]](xNode: Node, yNode: Node, cost: T)

  def computeMinimumSpanningTreeUsingPrim(): UndirectedGraph[T] =
    computeMinimumSpanningTree(nodes.tail, UndirectedGraph(List(nodes.head), Nil))

    private def computeMinimumSpanningTree(leftNodes: List[Node], mst: UndirectedGraph[T]): UndirectedGraph[T] = {
    leftNodes match {
      case Nil => mst
      case _ =>
        val minCostEdge = minCost(cost(leftNodes, mst)) // xNode belongs to leftNodes, and yNode belongs to mst
        if (minCostEdge == None) throw new Error("disconnected graph")
        val updatedLeftNodes = leftNodes diff List(minCostEdge.get.xNode)
        val updatedMst = UndirectedGraph(
              minCostEdge.get.xNode :: mst.nodes,
              toEdge(minCostEdge.get) :: mst.edgetList)
        computeMinimumSpanningTree(updatedLeftNodes, updatedMst)
    }
  }

  private def toEdge[T <% Ordered[T]](nodesEdge: NodesEdge[T]): Edge[T] =
    Edge(nodesEdge.xNode.name, nodesEdge.yNode.name, nodesEdge.cost)

  private def cost(outsideNodes: List[Node], graph: UndirectedGraph[T]): List[NodesEdge[T]] =
    for {
      node <- outsideNodes
      minCostEdgeNodeToGraph <- minCostEdgeOfNodeToGraph(node, graph.nodes)

    } yield minCostEdgeNodeToGraph

  private def minCost[T <% Ordered[T]](nodesEdgeList: List[NodesEdge[T]]): Option[NodesEdge[T]] = {
    val min: Option[NodesEdge[T]] = None
    nodesEdgeList.foldLeft(min)((comp, itm) =>
      if (comp != None) {
        if (comp.get.cost > itm.cost) Some(itm) else comp
      } else {
        Some(itm)
      })
  }

  private def cost(nodeA: Node, nodeB: Node): Option[T] = {
    val costItem = edgetList.filter(item => {
      (item.xNodeName == nodeA.name && item.yNodeName == nodeB.name) ||
        (item.yNodeName == nodeA.name && item.xNodeName == nodeB.name)
    })
    if (costItem != Nil) Some(costItem.head.cost) else None
  }

  private def minCostEdgeOfNodeToGraph(node: Node, graph: List[Node]): Option[NodesEdge[T]] = {
    val edges = for {
      n <- graph
      cost <- cost(n, node)
    } yield NodesEdge(node, n, cost)
    minCost(edges)
  }
}

To test it you can use something like this:

package org.madeforall.extractor.test

import org.scalatest._

import org.scalatest.matchers._

import org.madeforall.graph.mst.prim._

/**

 * @author Nicolae Caralicea

 * @version 1.0, 26/01/2013

 */

class TestMst extends FlatSpec with ShouldMatchers {

    

  "The minimal spanning resulted whn using the Prim's alghorith" should "be like" in {

    val graph: UndirectedGraph[Double] = UndirectedGraph(

      List(

        Node("A"), Node("B"), Node("C"), Node("D"),

        Node("E"), Node("F"), Node("G"), Node("H"),

        Node("M"), Node("N")),

      List(

        Edge("A", "B", 9.0),

        Edge("A", "F", 6),

        Edge("A", "G", 3),

        Edge("B", "G", 9),

        Edge("B", "M", 8),

        Edge("B", "C", 18),

        Edge("C", "M", 10),

        Edge("C", "N", 3),

        Edge("C", "D", 4),

        Edge("D", "N", 1),

        Edge("D", "E", 4),

        Edge("E", "F", 9),

        Edge("E", "H", 9),

        Edge("E", "M", 7),

        Edge("F", "G", 4),

        Edge("F", "H", 2),

        Edge("H", "G", 2),

        Edge("H", "M", 8),

        Edge("M", "N", 9),

        Edge("M", "G", 9),

        Edge("N", "E", 5)))

    assert(graph.computeMinimumSpanningTreeUsingPrim === UndirectedGraph(

        List(Node("B"), Node("C"), Node("N"), Node("D"), Node("E"), Node("M"), Node("F"), Node("H"), Node("G"), Node("A")),

        List(Edge("B","M",8), Edge("C","N",3), Edge("N","D",1), Edge("D","E",4), Edge("E","M",7), Edge("M","H",8), Edge("F","H",2),

            Edge("H","G",2), Edge("G","A",3))))

  }

    

}

If you want to use and contribute in any way to this project/code here is the link to its Github repository:

https://github.com/ncaralicea/madeforall

Simple Scala Text Recognition Patterns

So many times I wanted to be able to extract email addresses, links, specific html tags, simple chunks of code, you name it from simple text, html content, code, etc.

But, every time I ended up looking for the right REGEX expressions, tweaking them, throwing them into my code and forget everything the day after. Next time I would start over again and again.

I think that this library could preserve all these efforts, so bear with me to see how Scala with its nice features like Extractors, REGEX, and Manifest classes can make your life much easier.


Let's assume that we have some text based content (txt, html, etc) and that our goals are the followings:

• We want to be able to easily extract email addresses, links, images, etc from the above content
• We want to have a decent and common data format of what we extract
• We want to easily add new patterns to the existent text recognition patterns, so we would be able to recognize more patterns in our text based contents

The madeforall's extractor library is a Scala based library that is meant to help us reach the above goals.

Here is a simple description of how to use and extend this library:

We create a RecognizableItemsExtractor object, to which we pass as a parameter an RecognitionPattern object

Any RecognitionPattern object should:
- implement the unapply extraction method (Scala based extractor)
- mix in the RecognitionPattern trait
 
For instance, to support email recognition, we could do the followings:

case class Email(user: String, domain: String) extends Recognizable {

  override def toString() = {

    user + "@" + domain

  }

}

object EmailRecognitionPattern extends RecognitionPattern {

  // The extraction method

  def unapply(str: String): Option[(String, String)] = {

    val parts = str split "@"

    if (parts.length == 2) Some(parts(0), parts(1)) else None

  }

  // email regex

  val regexPattern = """(?i)\b[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}\b""".r

  def recognize(value: String): Option[Recognizable] = {

    value match {

      case EmailRecognitionPattern(user, domain) =>

        Some(Email(user, domain))

      case _ =>

        None

    }

  }

}

Then, to extract all the emails from our text we could do the followings:

val textToAnalyze: String = "<<some content>>"

val recog = RecognizableItemsExtractor(List(EmailRecognitionPattern))

val emailList: List[Recognizable] = recog.analyzeText(textToAnalyze)

If we want to extract emails and links we can also add more recognition patterns to the above RecognizableItemsExtractor.

RecognizableItemsExtractor(List(EmailRecognitionPattern, LinkRecognitionPattern))

val emailAndLinkList: List[Recognizable] = recog.analyzeText(textToAnalyze)

The above emailAndLinkList list contains both emails and links.
To filter out emails we could use the following filterByType function.

val onlyEmailList = recog.filterByType[Email](emailAndLinkList)

Here is the definition of the RecognizableItemsExtractor's filterByType function:

  def filterByType[T <: Recognizable](t: List[Recognizable])(implicit mf: Manifest[T]) =

    t.filter(e => mf.erasure.isInstance(e))

It is based on Scala class manifest feature, that is helping the runtime
with the type information provided as hint by the Scala compiler.
Type erasure is still present in Scala like in Java.
The creators of Scala gave us this helpful manifest class support to overcome
the JVM's type erasure limitations.

If you want to use and contribute in any way to this project here is the link to its Github repository:

https://github.com/ncaralicea/madeforall





      

MadeForAll (Alfa) - Social collaboration & Knowledge Sharing platform

MadeForAll is a platform where people can easily create, search, and share information. 


They can share this information privately with their own groups or they can also make the information available to anyone.


It is people's choice to define their own data structures that represent the best their knowledge. 


Either programmers or just web addicts in searching for new ways of doing collaboration with their peers, MadeForAll could be the answer.


You might also get a better idea of what you can do on MadeForAll from some of its screenshots,


The website is just in its Alpha stage and any suggestions are more than welcomed.


Feel free to contact us or post comments on MadeForAll.


I will soon expose its API, so MadeForAll could be easily integrated into your own applications.


I might also opensource the whole MadeForAll platform so other developers could join and give a hand too.
It is too overwhelming to work alone on it and I feel like it would take me forever to finish it, so I am really optimistic that I would open source MadeeForAll eventually.


So, if you are a developer that really loves Scala, Erlang, NoSQL, Spring, and other great technologies, and you also want to contribute to MadeForAll, there are many exiting things waiting ahead for you.
  
For now, just have a look and give me some suggestions if you feel it.

Scala – Get a taste of implicit parameters through Quicksort

Why is Scala great?

I'm tempted simply to state that Scala is great. However, I know that many developers have not yet heard of it, so I'll try to explain why that's true.

Why? Because it offers a number of goodies that other programming languages don't.

For those who don't know this yet, I would ask them to imagine shopping for the best 10-year-long package tour. 

I wouldn't say that everything inside Scala's Dream Package is unique or without peer, but the price you'll pay and the goodies you'll get make it by far your best overall choice for those years to come.

What are the features that make Scala so great? Among other things, it's concise, elegant, type-safe, object-oriented, functional, extremely fast, compatible/inter-operable with Java, has great pattern matching, and uses a powerful actor model borrowed form Erlang.

Wouldn't that be a delightful 10-year tour on the Scala boat?

So, give it a shot and get onboard -- there's plenty of space, and everyone's friendly too!

In other words, Scala is versatile enough to be used everywhere, and it has a large community with excellent support.

I realize that a newcomer can hardly avoid initial sea-sickness, but there are at least 10 years ahead of real joy. A few months of hardship will more than repay, trust me.

I would like to try to convince you by showing you one of Scala's unique features  -- Implicit Parameters.

What are they? Some parameters used to define a method can be marked with the keyword 'implicit'. Where are such parameters used?

Under certain circumstances if the developer has not provided some parameters in a function call, the compiler will try to implicitly insert the values for all those missing parameters, so the code will be properly compiled and the function call will be properly executed.

In the coming examples I will try to gradually show you when and why is good to have implicit parameters.

I will try to use Scala to implement  the Quicksort algorithm.
Far from being the fastest Scala implementation of Quicksort the implementation shown here is just good enough for our purpose.

Here at the http://en.wikipedia.org/wiki/Quicksort link you can find more about Quicksort.

A naive scala implementation - it only addresses the Int type

object NaiveQuickSort {

  def qsort(list : List[Int]) : List[Int] = {

    list match {

      case List() => List()

      case h :: tail => qsort(tail.filter(_ <= h)) ::: List(h) 
                         ::: qsort(tail.filter(_ > h))

    }

  }

  def main(args: Array[String]): Unit = {

    println(qsort(List(2, 4, 1, 6, 5)))

  }

}

the displayed result is: List(1, 2, 4, 5, 6)

A parametrized implementation - it is a parameteriezed implementation, so it could be used for any types as long as a comparison function for that types has been explicitly provided. You can see the explicitly provided parameter when calling the qsort function. This might be avoided though, but this is a another great topic related to the currying concept.

object ParameterizedQuickSort {

  def qsort[T](less : (T, T) => Boolean)(list : List[T]) : 
    List[T] = {

    list match {

      case List() => List()

      case h :: tail =>

        (qsort(less)(tail.filter(less(_, h)))) ::: List(h) :::       
        (qsort(less)(tail.filter(! less(_, h))))

    }

  }

  def main(args: Array[String]): Unit = {

    println(qsort((x: Int, y: Int) => x < y)(List(2, 4, 1, 6, 
         5)))

    println(qsort((x: String, y: String) => x < y)(List("violin", 
     "piano","whistle", "guitar","saxophone")))

   }

}

A parametrized implementation with implicit parameters

As you can see there are 2 lines that defines the comparison functions for the Int and String types. These lines basically let the compiler know what values it can implicitly supply when necessary.

  implicit val lessIntOp = (x: Int, y: Int) => x < y

  implicit val lessStringOp = (x: String, y: String) => x < y

Having the implicit marker for the 'less' parameter of the following line lets the compiler know which parameters of the qsort function might be missing in a function call, so the compiler could insert them when needed.

def qsort[T](list : List[T])(implicit less : (T, T) => Boolean)

  : List[T]

In the following lines the 'less' parameter is not provided and the code still compiles and is properly executed.


println(qsort(List(2, 4, 1, 6, 5)))

println(qsort(List("violin", "piano","whistle", 

  "guitar","saxophone")))

And, here is the whole code you can use to test this.

object ImplicitParameterizedQuickSort {

  implicit val lessIntOp = (x: Int, y: Int) => x < y

  implicit val lessStringOp = (x: String, y: String) => x < y

  def qsort[T](list : List[T])(implicit less : (T, T) => Boolean)
  : List[T] = {

     list match {

      case List() => List()

      case h :: tail =>

        qsort(tail.filter(less(_, h))) ::: List(h) :::  
        qsort(tail.filter(! less(_, h)))

     }

  }

  def main(args: Array[String]): Unit = {

    println(qsort(List(2, 4, 1, 6, 5)))

    println(qsort(List("violin", "piano","whistle",  
      "guitar","saxophone")))

   }

}


This is it. Just a sec.
Please look at the next chunk of Erlang code (the code was taken from Erlang Programming - Francesco's book):


qsort([]) -> [];
qsort([X | Xs] ->
  qsort([Y || Y <- Xs, Y =< X]) ++ [X] ++ qsort([Y || Y <-Xs, Y > X]).


and compare it with this:

def qsort[T](list : List[T])(implicit less : (T, T) => Boolean)

  : List[T] = {

     list match {

      case List() => List()

      case h :: tail =>

        qsort(tail.filter(less(_, h))) ::: List(h) :::  

        qsort(tail.filter(! less(_, h)))

  }

}

They look pretty similar don't they?


This is another reason Scala is just great. It resembles Erlang in so many ways.

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.

Dependency Graphs - A Generic Approach In Java

I recently came across the dependency graph topic that was not too familiar to me and tried to put together something simple and working. A sheer background of graphs I already had but never really tried to seriously play with them.
Refusing to read all the involved math in dealing with such matter, my first two tries of having something working were doomed to fail.
I still kept refusing to get more educated in the matter and tried one more time still repeating to myself - "The approach should be just common sense - we bump into graphs everywhere from transit buses to web, so why math for it- we should not be that dumb"


Here you can find some code that works fine for me, so feel free to use it. In my next posts I might add something to it, or implement it in Scala. Let me know if this works for you or if you need some extra features. I am open for any suggestions.


I also added the graph which nodes where generated by the following statements:
(Note that the order the following statements are executed does not matter. The result should be the same)

        graph.addDependency("a", "b");
        graph.addDependency("a", "c");
        graph.addDependency("a", "f");
        graph.addDependency("c", "d");
        graph.addDependency("d", "g");
        graph.addDependency("f", "d");
        graph.addDependency("h", "e");

As you can see the result should be this:[a, h, b, c, f, e, d, g]

To test the code use this:

package org.madeforall.graph.test;

import java.util.ArrayList;
import java.util.List;

import org.madeforall.graph.Graph;
import org.madeforall.graph.NodeValueListener;

public class TestDependecyGraph {
    public static void main(String[] args) {
        testWithGenericInt();
        testWithGenericString();
    }

    public static void testWithGenericInt() {
        final List<Integer> nodeValueList = new ArrayList<Integer>();
        Graph<Integer> graph = new Graph<Integer>(new NodeValueListener<Integer>() {
            public void evaluating(Integer nodeValue) {
                nodeValueList.add(nodeValue);
            }
        });
        graph.addDependency(1, 2);
        graph.addDependency(1, 3);
        graph.addDependency(3, 4);
        graph.addDependency(3, 5);
        graph.addDependency(5, 8);
        graph.addDependency(2, 7);
        graph.addDependency(2, 9);
        graph.addDependency(2, 8);
        graph.addDependency(9, 10);
        graph.generateDependencies();

        System.out.println(nodeValueList);

    }

    public static void testWithGenericString() {
        final List<String> nodeValueList = new ArrayList<String>();
        Graph<String> graph = new Graph<String>(new NodeValueListener<String>() {
            public void evaluating(String nodeValue) {
                nodeValueList.add(nodeValue);
            }
        });
        graph.addDependency("a", "b");
        graph.addDependency("a", "c");
        graph.addDependency("a", "f");
        graph.addDependency("c", "d");
        graph.addDependency("d", "g");
        graph.addDependency("f", "d");
        graph.addDependency("h", "e");
        graph.generateDependencies();
        System.out.println(nodeValueList);

    }
}

The first and the second argument of the addDependency method of the Graph class are some two arbitrarily chosen nodes of the oriented graph. Watch out for circular dependencies, because I did not take care of them yet.


Here are the classes.

package org.madeforall.graph;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Set;

/**

 *

 * Represents a graph of nodes. Every node is of GraphNode type and it has set a

 * value of the generic type <T>. It basically derives an evaluation order out

 * of its nodes. A node gets the chance to be evaluated when all the incoming

 * nodes were previously evaluated. The evaluating method of the

 * NodeValueListener is used to notify the outside of the fact that a node just

 * got the chance to be evaluated. A value of the node that is of the generic

 * type <T> is passed as argument to the evaluating method.

 *

 *

 * @author nicolae caralicea

 *

 * @param <T>

 */

final public class Graph<T> {

    /**

     * These are basically the nodes of the graph

     */

    private HashMap<T, GraphNode<T>> nodes = new HashMap<T, GraphNode<T>>();

    /**

     * The callback interface used to notify of the fact that a node just got

     * the evaluation

     */

    private NodeValueListener<T> listener;

    /**

     * It holds a list of the already evaluated nodes

     */

    private List<GraphNode<T>> evaluatedNodes = new ArrayList<GraphNode<T>>();

    /**

     * The main constructor that has one parameter representing the callback

     * mechanism used by this class to notify when a node gets the evaluation.

     *

     * @param listener

     *            The callback interface implemented by the user classes

     */

    public Graph(NodeValueListener<T> listener) {

        this.listener = listener;

    }

    /**

     * Allows adding of new dependicies to the graph. "evalFirstValue" needs to

     * be evaluated before "evalAfterValue"

     *

     * @param evalFirstValue

     *            The parameter that needs to be evaluated first

     * @param evalAfterValue

     *            The parameter that needs to be evaluated after

     */

    public void addDependency(T evalFirstValue, T evalAfterValue) {

        GraphNode<T> firstNode = null;

        GraphNode<T> afterNode = null;

        if (nodes.containsKey(evalFirstValue)) {

            firstNode = nodes.get(evalFirstValue);

        } else {

            firstNode = createNode(evalFirstValue);

            nodes.put(evalFirstValue, firstNode);

        }

        if (nodes.containsKey(evalAfterValue)) {

            afterNode = nodes.get(evalAfterValue);

        } else {

            afterNode = createNode(evalAfterValue);

            nodes.put(evalAfterValue, afterNode);

        }

        firstNode.addGoingOutNode(afterNode);

        afterNode.addComingInNode(firstNode);

    }

    /**

     * Creates a graph node of the <T> generic type

     *

     * @param value

     *            The value that is hosted by the node

     * @return a generic GraphNode object

     */

    private GraphNode<T> createNode(T value) {

        GraphNode<T> node = new GraphNode<T>();

        node.value = value;

        return node;

    }

    /**

     *

     * Takes all the nodes and calculates the dependency order for them.

     *

     */

    public void generateDependencies() {

        List<GraphNode<T>> orphanNodes = getOrphanNodes();

        List<GraphNode<T>> nextNodesToDisplay = new ArrayList<GraphNode<T>>();

        for (GraphNode<T> node : orphanNodes) {

            listener.evaluating(node.value);

            evaluatedNodes.add(node);

            nextNodesToDisplay.addAll(node.getGoingOutNodes());

        }

        generateDependencies(nextNodesToDisplay);

    }

    /**

     * Generates the dependency order of the nodes passed in as parameter

     *

     * @param nodes

     *            The nodes for which the dependency order order is executed

     */

    private void generateDependencies(List<GraphNode<T>> nodes) {

        List<GraphNode<T>> nextNodesToDisplay = null;

        for (GraphNode<T> node : nodes) {

            if (!isAlreadyEvaluated(node)) {

                List<GraphNode<T>> comingInNodes = node.getComingInNodes();

                if (areAlreadyEvaluated(comingInNodes)) {

                    listener.evaluating(node.value);

                    evaluatedNodes.add(node);

                    List<GraphNode<T>> goingOutNodes = node.getGoingOutNodes();

                    if (goingOutNodes != null) {

                        if (nextNodesToDisplay == null)

                            nextNodesToDisplay = new ArrayList<GraphNode<T>>();

                        // add these too, so they get a chance to be displayed

                        // as well

                        nextNodesToDisplay.addAll(goingOutNodes);

                    }

                } else {

                    if (nextNodesToDisplay == null)

                        nextNodesToDisplay = new ArrayList<GraphNode<T>>();

                    // the checked node should be carried

                    nextNodesToDisplay.add(node);

                }

            }

        }

        if (nextNodesToDisplay != null) {

            generateDependencies(nextNodesToDisplay);

        }

        // here the recursive call ends

    }

    /**

     * Checks to see if the passed in node was aready evaluated A node defined

     * as already evaluated means that its incoming nodes were already evaluated

     * as well

     *

     * @param node

     *            The Node to be checked

     * @return The return value represents the node evaluation status

     */

    private boolean isAlreadyEvaluated(GraphNode<T> node) {

        return evaluatedNodes.contains(node);

    }

    /**

     * Check to see if all the passed nodes were already evaluated. This could

     * be thought as an and logic between every node evaluation status

     *

     * @param nodes

     *            The nodes to be checked

     * @return The return value represents the evaluation status for all the

     *         nodes

     */

    private boolean areAlreadyEvaluated(List<GraphNode<T>> nodes) {

        return evaluatedNodes.containsAll(nodes);

    }

    /**

     *

     * These nodes represent the starting nodes. They are firstly evaluated.

     * They have no incoming nodes. The order they are evaluated does not

     * matter.

     *

     * @return It returns a list of graph nodes

     */

    private List<GraphNode<T>> getOrphanNodes() {

        List<GraphNode<T>> orphanNodes = null;

        Set<T> keys = nodes.keySet();

        for (T key : keys) {

            GraphNode<T> node = nodes.get(key);

            if (node.getComingInNodes() == null) {

                if (orphanNodes == null)

                    orphanNodes = new ArrayList<GraphNode<T>>();

                orphanNodes.add(node);

            }

        }

        return orphanNodes;

    }

}

package org.madeforall.graph;

import java.util.ArrayList;

import java.util.List;

/**

 *

 * It represents the node of the graph. It holds a user value that is passed

 * back to the user when a node gets the chance to be evaluated.

 *

 * @author nicolae caralicea

 *

 * @param <T>

 */

final class GraphNode<T> {

    public T value;

    private List<GraphNode<T>> comingInNodes;

    private List<GraphNode<T>> goingOutNodes;

    /**

     * Adds an incoming node to the current node

     *

     * @param node

     *            The incoming node

     */

    public void addComingInNode(GraphNode<T> node) {

        if (comingInNodes == null)

            comingInNodes = new ArrayList<GraphNode<T>>();

        comingInNodes.add(node);

    }

    /**

     * Adds an outgoing node from the current node

     *

     * @param node

     *            The outgoing node

     */

    public void addGoingOutNode(GraphNode<T> node) {

        if (goingOutNodes == null)

            goingOutNodes = new ArrayList<GraphNode<T>>();

        goingOutNodes.add(node);

    }

    /**

     * Provides all the coming in nodes

     *

     * @return The coming in nodes

     */

    public List<GraphNode<T>> getComingInNodes() {

        return comingInNodes;

    }

    /**

     * Provides all the going out nodes

     *

     * @return The going out nodes

     */

    public List<GraphNode<T>> getGoingOutNodes() {

        return goingOutNodes;

    }

}

package org.madeforall.graph;

/**

 * The main mechanism used for notifying the outside of the fact that a node

 * just got its evaluation

 *

 * @author nicolae caralicea

 *

 * @param <T>

 */

public interface NodeValueListener<T> {

    /**

     *

     * The callback method used to notify the fact that a node that has assigned

     * the nodeValue value just got its evaluation

     *

     * @param nodeValue

     *            The user set value of the node that just got the evaluation

     */

    void evaluating(T nodeValue);

}

Dependency Graphs - A Generic Approach In Java by nicolae caralicea is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.