## 12/18/08

### Playing with Scala 5 ½: More variations

As James pointed out, the implicit conversion creates a new object every time we convert the Node to Ordered[Node], and although the JVM and the GC can deal pretty well with that kind of scenario, it will be better if we can avoid the creation of the object (BTW, the fact that Scala can leverage years of work on JIT optimizations is something that shouldn't be taken lightly... I still want tail call optimization, though)

We need to add the Ordered trait for Node somewhere in the hierarchy. The reasonable place is when we add the Weight trait (once we have weight we can compare the nodes):

class DfsNode extends NodeImpl with Weight with Ordered[DfsNode]{

...

def compare(y: Node): Int = this.weight.compare(y.weight)

}

Now we can compare the nodes by their weight: “lighter” nodes are before “heavier” nodes, but the comparation is not what we need for the priority queue, we need to reverse the the ordering.

The most immediate way is just reverse DfsNode's comparation function:

def compare(y: Node): Int = -this.weight.compare(y.weight)

but this has the undesirable effect of reversing all the node comparations, and most of the time I'll bet we want to have the lighter nodes before the heavier ones, the reverse is counter-intuitive (and the potential source of nightmares). The solution? Let's create our particular flavor of DfsNode with the comparation reversed to use it in the PriorityQeue:

class PQNode extends DfsNode {

override def compare(y: Node): Int = -super.compare(y)

}

And we just need to change our newNode method to return PQNodes instead of DfsNodes:

protected def newNode: Node = new PQNode

For extra points on modularization, we can extract those changes and the code related to the algorithm in a subclass of DfsGraph.

Here is the complete code:

`package dfs2; abstract class Graph { type Edge type Node <: NodeIntf abstract class NodeIntf { def connectWith(node: Node): Edge } def nodes: Set[Node] def edges: Set[Edge] def addNode: Node} abstract class DirectedGraph extends Graph { type Edge <: EdgeImpl class EdgeImpl(origin: Node, dest: Node) { def from = origin def to = dest } class NodeImpl extends NodeIntf { self: Node => def connectWith(node: Node): Edge = { val edge = newEdge(this, node) edges = edges + edge edge } } protected def newNode: Node protected def newEdge(from: Node, to: Node): Edge var nodes: Set[Node] =Set() var edges: Set[Edge] =Set() def addNode: Node = { val node = newNode nodes = nodes + node node }} trait Weight { var weight= Float.PositiveInfinity} import scala.collection.mutable.PriorityQueue; class DfsGraph extends DirectedGraph { class DfsNode extends NodeImpl with Weight with Ordered[DfsNode]{ var previous: DfsNode = _ var label:String = _ var nodeEdges: Set[Edge] = Set() override def connectWith(node: Node): Edge = { val newEdge=super.connectWith(node) nodeEdges = nodeEdges + newEdge newEdge } def -->(n2:Node):DfsEdge =connectWith(n2) override def toString()= label+ " w:"+weight def compare(y: Node): Int = this.weight.compare(y.weight) } class DfsEdge(origin:Node, dest:Node) extends EdgeImpl(origin, dest) with Weight { override def toString()= from.label+"-->"+to.label+" w:"+weight } def addNewNode(l:String):Node={ val newNode=super.addNode newNode.label=l newNode } type Node= DfsNode type Edge= DfsEdge protected def newEdge(from: Node, to: Node): Edge = new DfsEdge(from,to) protected def newNode: Node = new DfsNode } class DijkstraSPGraph extends DfsGraph { class PQNode extends DfsNode { override def compare(y: Node): Int = -super.compare(y) } override protected def newNode: Node = new PQNode def shortestPath(start: DfsNode, end: DfsNode) = { val unvisited=new PriorityQueue[Node]() unvisited++=(nodes) start.weight=0 while (!unvisited.isEmpty) { val vertx=unvisited.dequeue for (v <- vertx.nodeEdges if canImprove(v)){ unvisited+improveDistance(v) } } } def canImprove(a:Edge)=(a.from.weight+a.weight< a.to.weight) def improveDistance(a:Edge) ={ val v=a.to v.weight=a.from.weight+a.weight v.previous=a.from v } def pathToStart(end:DfsNode):List[DfsNode] = { if (end == null) Nil else end :: pathToStart(end.previous) }} object Example extends Application { val graph = new DijkstraSPGraph val n1=graph addNewNode "start" val n2=graph addNewNode "n2" val n3=graph addNewNode "n3" val n4=graph addNewNode "n4" val n5=graph addNewNode "n5" val n6=graph addNewNode "end" graph addNewNode "alone" n1-->n2 weight=2 n1-->n3 weight=1 n2-->n4 weight=1 n3-->n4 weight=3 n2-->n5 weight=1 n4-->n6 weight=1 n5-->n6 weight=3 n1-->n6 weight=7 n1-->n4 weight=10 graph.shortestPath(n1,n6) println("Path") graph.pathToStart(n6).reverse.map(println(_)) }`