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(_))

}

12/14/08

Playing with Scala 5: improving code, use of views and comprehensions

After reading about different optimization to pathfinding algorithms, I decided to improve my Dijkstra implementation by using a priority queue instead of a set for the unvisited nodes. Using the “weight” of the vertex as the priority, we can avoid searching the whole set for the minimum and we reduce the cost of the operation from O(n) to O(log n).

The first change is replace the set with Scala's priority queue:


val unvisited=new PriorityQueue[Node]()




But as it is, it will not compile: the priority queue's signature is


class PriorityQueue[A](implicit view$1 : (A) => Ordered[A]) extends ResizableArray[A] with CloneableCollection


You need to provide an implicit conversion from the parameter type A to the type Ordered[A]. But nothing to worry about: is as easy as


implicit def node2ordered(n: Node): Ordered[Node] = new Ordered[Node] {

//reverse the comparation so highest priority = lower cost

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

}


Look at the improveDistance function, it does two things: filters the nodes and updates the distance if we can improve it. I think is better if we split into two different functions, separating the filtering from the updating, so instead of:


def improveDistance(a:Edge) ={
if (a.from.weight+a.weight< a.to.weight) {
a.to.weight=a.from.weight+a.weight
a.to.previous=a.from
}
}


we get:

def canImprove(a:Edge)=(a.from.weight+a.weight< a.to.weight)

and

def improveDistance(a:Edge) ={

a.to.weight=a.from.weight+a.weight

a.to.previous=a.from

a.to

}


Then, instead of a function map over the nodeEdges, we have to filter and then map:


vertx.nodeEdges.map(improveDistance(_))


is replaced by


vertx.nodeEdges.filter(canImprove(_))).map(improveDistance(_)


that gives a better picture of the steps involved.

As we need to add the updated nodes to the priority queue so they can “float” to the top, the line would look like:


unvisited++ (vertx.nodeEdges.filter(canImprove(_))).map(improveDistance(_))


But I don't really think the explicit use of map and filter helps readability.

Enter Scala's for comprehensions: we can replace the map/filter with a comprehension:


for (v <- vertx.nodeEdges if canImprove(v)){

unvisited+improveDistance(v)

}

Nothing fantastic, but an improvement, isn't it?

For future posts, I'm planning on generalizing the algorithm into a A* pathfinding with different heuristic functions... stay tuned!