I’m implementing the Floyd-Warshall multiple-source shortest path algorithm in Scala. I haven’t debugged it yet, so don’t copy my code and expect it to work.
Nevertheless, there are a couple of things I find exceedingly ugly in my implementation, but don’t know of a better way of doing them. Maybe someone can give me some advice???
The algorithm starts with a structure describing the graph: adj:Map[A,Set[A]] which specifies that any node of type A connects to zero or more other nodes of the same type A.
The function, computeDistancePredecessors, computes two things. 1) d, a distance map, which maps each pair (x,y) of vertices to the integer distance from x to y. and 2) pred, a predecessor map, which maps each pair (x,y) of vertices to the vertex which is the predecessor of y along the shortest path from x to y.
Two things that are ugly (in my opinion).
- I’m modeling infinite distance as simply pairs missing from the Map. This has ugly consequences.
val d is effectively an initial value of a 2x2 matrix, implemented as a Map[(A,A),Int]. If vertex x is adjacent to vertex y in the graph, then d(x -> y) is the integer distance from x to y, and d(x -> x) = 0 for all vertices. In my implementation, if x and y are not adjacent, then d.get(x->y) = None.
Many implementations of Floyd-Marshall use a special value for INFINITY, which as I understand Scala Int does not support. This special value works with assignment, and + and < etc in intuitive ways. e.g., INFINITY + x = INFINITY for all x.
My implementation is ugly because I have 5 cases, each one representing the situation that a different distance is INFINITY. The classic Floyd-Marshall reduces these 5 cases to just 2 cases.
- I am using two concentric
flatMapcalls to immutably derive the nextditeration from the currentd. There is one iteration per value ofkwhich is realized in my code as aadj.foldLeft(d)(loop).
The ugly thing is that I also need to derive a new value of pred on each call to loop. So I compute this pred = pred + ((row -> col) -> pred(k -> col)) which modifies the value of the free var.
I don’t know how to do this better, as I don’t know how to make two concentric calls to flatMap take a pair of Maps and construct a new pair of maps, whereas normally flatMap of flatMap takes a Map and contracts a new Map.
There is a 3rd small issue described elsewhere which discusses the problem that concentric calls to flatMap unfortunately cannot be abbreviated using the for construct.
object FloydWarshall {
type ADJ[A] = Map[A,Set[A]]
def computeDistancePredecessors[A](adj:ADJ[A], source: A)(weight: Edge[A] => Int): (Map[(A,A),Int],Map[(A,A),A]) = {
val d: Map[(A, A), Int] = for {(src, dsts) <- adj
dst <- dsts + src
} yield (src -> dst) -> (if (src==dst) 0 else weight(Edge(src, dst)))
var pred: Map[(A, A), A] = for {(src, dsts) <- adj
dst <- dsts
} yield (src, dst) -> src
def loop(d: Map[(A, A), Int], k:A): Map[(A, A), Int] = {
val emptyMap: Map[(A, A), Int] = Map()
adj.flatMap { case (row, _) =>
adj.flatMap { case (col, _) =>
if (d.get(row -> col).isEmpty) {
if (d.get(row -> k).nonEmpty && d.get(k -> col).nonEmpty) {
pred = pred + ((row -> col) -> pred(k -> col)) // affecting the free var pred
Map((row -> col) -> (d(row -> k) + d(k -> col)))
} else { // either row->k or k->col is INFINITY
emptyMap
}
}
else { // d(row -> col) is empty, distance is INFINITY
if (d.get(row -> k).isEmpty || d.get(k -> col).isEmpty) { // either row->k or k->col is INFINITY
Map((row -> col) -> d(row -> col))
} else if (d(row -> k) + d(k -> col) < d(row -> col)) {
pred = pred + ((row -> col) -> pred(k -> col)) // affecting the free var pred
Map((row -> col) -> (d(row -> k) + d(k -> col)))
} else {
Map((row -> col) -> d(row -> col))
}
}
}
}
}
(adj.keys.foldLeft(d)(loop),pred)
}
def shortestPath[A](adj: ADJ[A], src: A, dst: A)(weight: Edge[A] => Int): Option[List[A]] = {
???
}
}
in the code. I have to test