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