Look at graph classes my previous post:
class Node (val label:String) {
var transitions: List[Arc] = Nil
var previous: Node = _
var weight= Float.PositiveInfinity
var visited = false
...
and
class Arc(var start: Node, var end: Node) {
var weight: Float = _
...
Don't you feel that something doesn't really fit? What are previous, visited, and weight are doing in Node? And weight in Arc?
Those properties doesn't really belong to a generic Node or Arc, they're specific for our algorithm. So, why having them there? Let's put those attributes on special cases of Node and Arc: DfsNode and DfsArc. But wait! Putting weight in both doesn't seem right either... we're defining the same thing twice! Weight is some kind of "cross-cutting" attribute.
Traits
Luckily modern OO languages had a very elegant way of solving this kind of problems by means of traits (usually are described as "interfaces with implementation" but a very powerful concept), so let's define our weight as a trait:
trait Weighted {
var weight= Float.PositiveInfinity
}
So we can clean our Node and Arc classes:
class Node(val label:String) {
var transitions: List[Arc] = Nil
override def toString()= {
label
}
def --> (end: Node):Arc={
transitions = new Arc(this,end) :: transitions
transitions.head
}
}
class Arc(var start: Node, var end: Node) {
override def toString()= {
start.label+"-->"+end.label
}
}
class DfsNode (label:String) extends Node(label) with Weighted {
var previous: DfsNode = _
var visited = false
override def toString()= {
super.toString+" w:"+weight+" p:"+previous
}
}
class Arc(var start: Node, var end: Node) {
override def toString()= {
start.label+"-->"+end.label
}
}
And I just need to change the signatures of the functions of the algorithm:
object Dijkstra {
def shortestPath(graph:Set[DfsNode], start: DfsNode, end: DfsNode) = {
var unvisited=graph
start.weight=0
while (!unvisited.isEmpty) {
val vertx=min(unvisited)
vertx.transitions.map(improveDistance(_))
unvisited=unvisited-vertx
}
}
def improveDistance(a:DfsArc) ={
if (a.start.weight+a.weight< a.end.weight) {
a.end.weight=a.start.weight+a.weight
a.end.previous=a.start
}
}
def min(nodes: Set[DfsNode]): DfsNode = {
nodes.reduceLeft((a:DfsNode,b:DfsNode)=>if (a.weight<b.weight) a else b )
}
def pathTo(end:DfsNode):List[DfsNode] = {
if (end == null)
Nil
else
end :: pathTo(end.previous)
}
}
What? It doesn't compile! node.transitions returns a list of Nodes and not DfsNodes! Argh! We've been bitten by the static typing! ("Ha-ha" will shout the Dynamic typing Nelson). I could use a .asInstanceOf[type] everywhere (like a Java cast) but it looks like a kludge and you have to put everywhere! There must be a better solution, after all, Scala is supposed to look elegant, right?
Views (implicit conversions)
Scala has a very interesting way of dealing with that kind of problem: by creating views using implicit conversions, we can convert from one type to other, the compiler will insert the appropriate call when needed. So I defined a conversion from Arc to DfsArc and Node to DfsNode:
object Implicits {
implicit def node2DfsNode(node:Node):DfsNode={
if (node.isInstanceOf[DfsNode])
node.asInstanceOf[DfsNode]
else {
var dfsNode=new DfsNode(node.label)
dfsNode.transitions=node.transitions
dfsNode
}
}
implicit def arc2DfsArc(arc:Arc):DfsArc={
if (arc.isInstanceOf[DfsArc])
arc.asInstanceOf[DfsArc]
else {
new DfsArc(arc.start,arc.end)
}
}
}
And now, everything will happly compile. The only caveat is as I defined the method --> returning an Arc and arc2DfsArc creating a new instance if I pass an Arc, the use of n1-->n2 weight=2 sets the weight in a new object and not in the object in the transitions collection. I'm sure there's a better solution, but meanwhile if we overrride the --> method in DfsNode will work:
def --> (end: DfsNode):DfsArc={
transitions = new DfsArc(this,end) :: transitions
transitions.head.asInstanceOf[DfsArc]
}
(Let me know if you want the full code posted)
