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!