# Immutable implementation of Bellman-Ford single source shortest path

I have three different questions about how to best implement a particular algorithm in Scala. I’ve implemented the Bellman-Ford single source shortest path algorithm within a `Graph` class. Below is the code for the `bellmanFord` method, but I think most of the `Graph` implementation is unimportant for this question, except that the type variable `A` is the vertex type. (maybe V is a better type variable for this purpose?)

``````case class Graph[A](Vertices: Set[A], Edges: Set[Edge[A]]) {
...
}
``````

The Bellman-Ford algorithm takes a graph and a `source` vertex and returns two values, 1) an mapping which given any vertex, `v`, gives the distance from the `source` to `v`. 2) a so-called precedence map which for any vertex, `v`, gives the preceding vertex along the shortest path from `source` to `v`. Using the precedence map, we can trace from anywhere back to the `source`.

A several questions about improving my implementation.

1. `bellmanFord` takes a `weight` function which maps each graph edge to a weight. I’ve implemented the edge weight as an integer, but I’d really like it to be more general. Can I replace `Edge[A] => Int` and `Map[A,Int]` with something more general to allow the return values of the `weight` function to be anything which supports `+` and `<` ?

2. The return value of `bellmanFord` is of type `(Map[A, Int], Map[A, A])`. I have to reuse this type several times within the algorithm on the local functions `relax` and `relaxationPass`. I’ve defined a type alias `DP` to reduce typing, but I suspect there’s a clearer way to do this. However, if I manage to encapsulate this ugly type into something more manageable, I need to make sure the `Int` in `Map[A,Int]` still is the same type as the `Int` in the previous `Edge[A] => Int`.

This somewhat complicated return type is avoided in mutating implementations such as in Python, because the bellmanFord function accepts two hash tables which it destructively modifies. I’d like to avoid these mutable objects.

1. the local function `relaxationPass` is a tail recursive function whose goal is to reduce the given `dp` several times, `i-1` times to be exact. Can’t I rewrite this somehow as call to some variant of fold/reduce which ignores its iteration variable?
``````def bellmanFord(source: A, weight: Edge[A] => Int): (Map[A, Int], Map[A, A]) = {
type DP = (Map[A, Int], Map[A, A])

def relax(edge: Edge[A], dp: DP): DP = {
val (distance, predecessor) = dp
val Edge(u, v) = edge
lazy val w = weight(edge)

(distance.get(u), distance.get(v)) match {
case (None, _) => dp
case (Some(du), None) =>
(distance + (v -> (du + w)), predecessor + (v -> u))
case (Some(du), Some(dv)) if (du + w < dv) =>
(distance + (v -> (du + w)), predecessor + (v -> u))
case _ => dp
}
}

def relaxationPass(i: Int, dp: DP): DP = {
if (i == 0)
dp
else
relaxationPass(i - 1, edges.foldLeft(dp) {
(dp: DP, edge: Edge[A]) => relax(edge, dp)
})
}

relaxationPass(Vertices.size, (Map((source -> 0)), Map()))
}
``````

BTW w.r.t. question (3), `relaxationPass` is supposed to run `Vertices.size - 1` times. I think there’s a bug (common off by one bug). I believe it is coded to run `Vertices.size` times instead. It will still get the same answer (Bellman-Ford still works). But this bug would be much easier to spot, if the tail-recursive function were replaced with a more declarative call to some sort of `fold-n-times` function.

With regards to 1, if I were you, I’d stick with `Doubles`. It sounds like that for the general case you want to have any A for which you have a seminormed vector space, but i doubt its worth it. https://github.com/typelevel/spire/blob/master/core/src/main/scala/spire/algebra/VectorSpace.scala has some inspiration if you do end up going in that direction

You could use `A <: Number`.

When you move from mutable state to immutable, your state becomes parameters and return values. I don’t see a way around this.

I might have something along the lines of what you’re looking for.

``````Vertices.indices.reverse.dropRight(1).foldLeft((Map((source -> 0)), Map())) ...
``````

Also, shout out to https://contributors.scala-lang.org/t/irrefutable-destructuring-patterns/2884 for your `relax` function. This doesn’t help you now but I want to spread awareness of the idea.

``````def relax(edge: Edge[A], dp: DP): DP = {
val (distance, predecessor) = dp
val Edge(u, v) = edge
``````

would become

``````def relax(Edge(u, v), (distance, predecessor): DP): DP = {
``````

.

1 Like

It seems to me that having automatically destructuring function arguments could only be a positive improvement. It would help programmers write less repetitive code, and this pattern occurs often. It is indeed a nice feature of clojure as I understand (not being an expert). It is also a feature of Common Lisp, but unfortunately in CL the feature is only available to macros, not to normal lambda functions (but as most things it can be added to CL lambda functions using macros, as I have done).

Given a function `f` and an initial argument `x`, I want to calculate `(f^n)(x)`. Where `f^n` is `f` composed of itself `n` times. There ought to be an easier way. Certainly I could write `composedToPower` as a helper function, but I feel like I’m reinventing something that already exists. And my re-invention is sure to be inferior. Especially in this case because the function is binary but returns a tuple. I’m not sure how to wrote `composedToPower` so a n-ary function can return an n-tuple.

Which of the following is most readable? For me, the third makes it much most clear how many times the edges get relaxed, but is obscured in that the reader must understand two different abstractions to read the code…

``````    def relaxationPass(i: Int, dp: DP): DP = {
if (i == 0)
dp
else
relaxationPass(i - 1, edges.foldLeft(dp) {
(dp: DP, edge: Edge[A]) => relax(edge, dp)
})
}
relaxationPass(Vertices.size, dp0)
``````

or

``````    def relaxEdges(dp:DP):DP = {
edges.foldLeft(dp) {
(dp: DP, edge: Edge[A]) => relax(edge, dp)
}
}
1.to(Vertices.size - 1).foldLeft(dp0){(dp,_)=>relaxEdges(dp)}
``````

or

``````
def relaxEdges(dp: DP): DP = {
edges.foldLeft(dp) {
(dp: DP, edge: Edge[A]) => relax(edge, dp)
}
}

def composeNtimes[B](initial:B,n:Int)(f:B=>B):B = {
(1 to n).foldLeft(initial)((a:B,ignored:Int) => f(a))
}

composeNtimes(dp0,Vertices.size - 1)(relaxEdges)
``````

Wouldn’t that also include complex numbers, which I’d of course like to exclude.

When I use Number, the `+` fails to resolve. I’m not sure what is causing this. But it also can’t resolve the `(v -> (du + w))`. At least IntelliJ thinks this has type `(A, NotInferredV1)`.

``````  def bellmanFord[B <: Number](source: A, zero:B, weight: Edge[A] => B): (Map[A, B], Map[A, A]) = {
type DP = (Map[A, B], Map[A, A])
val dp0: DP = (Map((source -> zero)), Map())

def relax(edge: Edge[A], dp: DP): DP = {
val (distance, predecessor) = dp
val Edge(u, v) = edge
lazy val w = weight(edge)

(distance.get(u), distance.get(v)) match {
case (None, _) => dp
case (Some(du), None) =>
(distance + (v -> (du + w)), predecessor + (v -> u))
case (Some(du), Some(dv)) if (du + w < dv) =>
(distance + (v -> (du + w)), predecessor + (v -> u))
case _ => dp
}
}
``````

Here is the error I get in IntelliJ.

The message from the compiler is somewhat less helpful.

``````Error:(23, 35) type mismatch;
found   : B
required: String
(distance + (v -> (du + w)), predecessor + (v -> u))
``````

I also realized that I don’t really need ‘<’ per se, If I know that the type is a semi-ring, with operations (op1,op2) then I can replace `a+b` in my function with `op1(a,b)` and `if (a < b+c) then a else b+c` with `op2(a,op1(b,c))`.

Rather than a seminormed vector space, I think all I really need is a semi-ring as I mention elsewhere. I can replace `a+b` and `if (a < b) then a else b` with `op1(a,b)` and `op2(a,b)`. I’m not claiming I know enough Scala to do that. But I think that’s the most general for my purpose.

Per Can't add object of type Number I gave you bad advice. jducoeur has a better idea of using Numeric. Although if you only need `<` then you could use Ordering instead.

Example usage:

``````def f[A](x0: A, x1: A)(implicit numeric: Numeric[A]): A = {
numeric.plus(x0, x1)
}
``````

`+` isn’t an operator on an arbitrary `A`, but there is a way to get one using an implicit conversion in `scala.math.Numeric.Implicits`.

``````import scala.math.Numeric.Implicits._
def f[A](x0: A, x1: A)(implicit numeric: Numeric[A]): A = {
x0 + x1
}
``````

Unfortunately it looks like each use of `+` will cause an allocation, so there is an (unnecessary) cost to pay.

Yes, but I need to use ‘+’ and also ‘<’. Does over type in Scala which supports < also support + ? That would be convenient for my needs, but surprising.

`Numeric` extends `Ordering`, so you get both if you use `Numeric`.

It does not seem to be the case.see here

What Number is that? java.lang.Number? That doesn’t have methods for + and <.

Also, note that Scala only auto-boxes its own AnyVal types. Anything you import from Java will never be an unboxed primitive.

Access to `Ordered` operations as symbols like `<` is a different import.

`import scala.math.Ordered.orderingToOrdered`.