/ FUNCTIONAL PROGRAMMING, DIJKSTRA

From Imperative to Functional Programming: the Dijkstra algorithm

This week, I’ll first implement the Dijkstra algorithm, then migrate the code to a more functional-friendly design.

This is the 4th post in the From Imperative to Functional Programming focus series. Other posts include:

  1. From Imperative to Functional Programming using Arrow
  2. From Imperative to Functional Programming, an approach
  3. From Imperative to Functional Programming: a grouping issue (and how to solve it)
  4. From Imperative to Functional Programming: the Dijkstra algorithm (this post)

The Dijkstra algorithm in a few words

A graph consists of both nodes and edges. An edge links two nodes.

There are different types of graphs: in weighted graphs, each edge has an associated weight.

In directed graphs, an edge can only be traveled in one direction; in undirected graphs, it can be traveled in any direction. Hence,

Dijkstra’s algorithm allows to find the shortest path in a graph. An unweighted graph can be considered a weighted graph where all weights are the same, and an edge in an undirected graph is the equivalent of two edges in each direction in a directed graph - with the same weight. Hence, any graph is a candidate structure for the algorithm, weighted or not, directed or not. The only requirement is that weights need to be positive.

The algorithm is as follows:

  1. Set the start node as the current node
  2. Repeat the following until the current node is the end node:
    1. Find all nodes accessible by edges from the current node
    2. Compute the overall weight to access unvisited nodes
    3. Mark the current node as visited
    4. Travel to the node with the less weight

A naive but working approach

Here is a straightforward implementation of the algorithm:

class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {

  private val evaluatedPaths = mutableMapOf<String, Int>()

  fun findShortestPath(start: String, end: String): Int {
    var current = start
    while (current != end) {
      current = updateShortestPath(current)
    }
    return evaluatedPaths.getValue(end)
  }

  private fun updateShortestPath(node: String): String {
    val subGraph = weightedPaths[node]
    for (entry in subGraph!!) {
      val currentDistance = evaluatedPaths
                               .getOrDefault(entry.key, Integer.MAX_VALUE)
      val newDistance = entry.value + evaluatedPaths.getOrDefault(node, 0)
      if (newDistance < currentDistance)
        evaluatedPaths[entry.key] = newDistance
    }
    evaluatedPaths.remove(node)
    return evaluatedPaths.minBy { it.value }?.key!!
  }
}

This snippet is definitely not FP-friendly, as it contains both:

  • mutable state e.g. evaluatedPaths
  • and loops - one while loop and one for loop

Migrating to Functional Programming

Migrating to FP means replacing:

  1. Loops with recursion
  2. Global mutable state with a passed around parameter

Additionally, Kotlin programmers might have noticed two usages of the !! operator: though the type system infers the value can be nullable, we as a developer tell the compiler it cannot.

Removing the !! crutch

There are two occurrences of !!. Both happen because when getting from a Map, nothing guarantees to the typesystem that there’s a corresponding key:

val map = mapOf("A" to 1)
val a = map.get("A")       // 1
val b = map.get("B")       // null

The type returned from get() is nullable.

To make it non-nullable in a more idiomatic way, we can throw an exception if the returned value is null:

val map = mapOf("A" to 1)
val a = map.get("A") ?: throw RuntimeException("Cannot happen")
val b = map.get("B") ?: throw RuntimeException("Will happen")

For the compiler, a and b are now of type String, even though at runtime, getting "B" will throw. While exceptions make functions partial and partial functions do not conform to FP, it’s a good step.

For iteration, it’s even easier. The two following lines are equivalent, but the second is more idiomatic:

for (entry in subGraph!!) { }
subGraph?.forEach { }

Replacing loops with recursion

There are two existing loops in the code: one while loop and one for loop. Let’s replace each of them with their Functional Programming equivalent - recursion. A recursion is a function that calls itself.

The findShortestPath() implementation can be replaced with:

fun findShortestPath(start: String, end: String): Int {
  recurseFindShortestPath(start, end)
  return evaluatedPaths.getValue(end)
}

The recurseFindShortestPath() function is recursive - as its name implies. A recursive function offers different branches, the most important one being the stop branch. In our case, the stop branch here is when the node has reached the end.

private fun recurseFindShortestPath(node: String, end: String): String {
  return if (node == end) end
  // else ...
}

The other branch contains the same code as before, with one small change: we compute the next node by calling the same function with the updated node.

private fun recurseFindShortestPath(node: String, end: String): String {
  return if (node == end) end
  else {
    // ... same code here
    val nextNode = evaluatedPaths.minBy { it.value }?.key
      ?: throw RuntimeException("Map was empty")
      recurseFindShortestPath(nextNode, end)
  }
}

The biggest issue with recursion is when calls pile upon one another on the stack. Because it’s based on real-world hardware, the stack has a limit, however high it is. When it’s reached, then the infamous StackOverflowError occurs. To avoid that, the compiler can actually generate the equivalent non-recursive bytecode.

This requires:

  • The function to be marked with tailrec
  • The last instruction of the function should be the recursive call

Because our function conforms to the second condition, it’s a no-brainer to just add the tailrec keyword to it and optimize the generated bytecode.

Removing global state one step at a time

Replacing the state with parameters is a bit harder than replacing loops with recursion. Hence, we will do it step-by-step: the first step is to move the global state to local state, but keep it mutable for the time being.

This is the initial code:

class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {

  private val evaluatedPaths = mutableMapOf<String, Int>()

  fun findShortestPath(start: String, end: String): Int {
    recurseFindShortestPath(start, end)
    return evaluatedPaths.getValue(end)
  }

  private tailrec fun recurseFindShortestPath(node: String, end: String): String {
    // ...

    recurseFindShortestPath(nextNode, end)
  }
}

After moving the state, the code becomes something like this:

class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {

  fun findShortestPath(start: String, end: String): Int {
      val paths = mutableMapOf<String, Int>()               (1)
      recurseFindShortestPath(start, end, paths)            (2)
      return paths.getValue(end)
  }

  private tailrec fun recurseFindShortestPath(node: String, (2)
                                               end: String,
                                            paths: MutableMap<String, Int>): String {
    // ...

    recurseFindShortestPath(nextNode, end, paths)           (2)
  }
}
1Move the mutable state inside the function
2Change the function signature to accept the state and pass it at every call

Add the state to the return value

Because we require immutable state, the next step is to also return the map along the existing return value.

class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {

  fun findShortestPath(start: String, end: String): Int {
    val (_, paths) = recurseFindShortestPath(start, end, mutableMapOf())  (1)
    return paths.getValue(end)
  }

  private tailrec fun recurseFindShortestPath(node: String,
                                               end: String,
                                             paths: MutableMap<String, Int>):
                                      Pair<String, MutableMap<String, Int>> { (2)
    return if (node == end) end to paths                                  (3)
    else {
      // ...
      recurseFindShortestPath(nextNode, end, paths)                       (4)
    }
  }
}
1Assign the Map to a dedicated variable using Kotlin destructuring
2Change the function signature to return the Map with the String, wrapping both into a Pair
3Assemble the String with the Map to return both
4Change the recursion call according to the new signature

Restrict mutability

Before going further, we will extract a huge part of the recurseFindShortestPath() function into a dedicated function in order to keep mutability contained to a smaller scope:

class Graph(private val weightedPaths: Map<String, Map<String, Int>>) {

  fun findShortestPath(start: String, end: String): Int { /* */ }

  private tailrec fun recurseFindShortestPath(node: String,
                                               end: String,
                                             paths: MutableMap<String, Int>):
                                      Pair<String, MutableMap<String, Int>> {
      return if (node == end) end to paths
      else {
          val updatedPaths = updatePaths(node, paths)
          val nextNode = updatedPaths.minBy { it.value }?.key
              ?: throw RuntimeException("Map was empty")
          recurseFindShortestPath(nextNode, end, updatedPaths)
      }
  }

  private fun updatePaths(node: String,
                         paths: MutableMap<String, Int>): MutableMap<String, Int> {
    // ...
  }
}

At that point, we want to start migrating from mutable state to immutable state. Let’s change the signature of the recurseFindShortestPath() function:

private tailrec fun recurseFindShortestPath(node: String,
                                             end: String,
                                           paths: Map<String, Int>):
                                    Pair<String, Map<String, Int>> {  (1)
  return if (node == end) end to paths
  else {
    val updatedPaths = updatePaths(node, paths.toMutableMap())        (2)
    val nextNode = updatedPaths.minBy { it.value }?.key
        ?: throw RuntimeException("Map was empty")
    recurseFindShortestPath(nextNode, end, updatedPaths)              (3)
  }
}
1Change the signature to use an immutable type instead of a mutable type i.e. from MutableMap to Map
2Pass a mutable type because the called function requires it
3No change in the function call

The next step is to change the signature of the called function in the same way. To keep the change small, we will keep using mutable state inside the function itself:

private fun updatePaths(node: String,
                       paths: Map<String, Int>): Map<String, Int> {     (1)
  var updatedPaths = paths                                              (2)
  weightedPaths[node]?.forEach {
    val currentDistance = paths.getOrDefault(it.key, Integer.MAX_VALUE)
    val newDistance = it.value + paths.getOrDefault(node, 0)
    if (newDistance < currentDistance)
      updatedPaths = updatedPaths + (it.key to newDistance)             (3)
  }
  return updatedPaths - node                                            (4)
}
1Only use immutable types in the function’s signature
2Assign the Map to a var, so it can be reassigned
3Create a new Map by adding a Pair instance to an existing Map, and reassign the var
4Create a new Map by removing the entry whose key is node from the Map i.e. remove the current node from the paths so it’s not evaluated again

At this point, it’s possible to extract the update of a single path into its own function. That will be help us to remove every trace of mutability:

private fun updatePaths(node: String, paths: Map<String, Int>): Map<String, Int> {
  var updatedPaths = paths
  weightedPaths[node]?.forEach {
    updatedPaths = updatedPaths + updatePath(paths, it, node)
  }
  return updatedPaths - node
}

The extracted function has no mutable state at all, and uses only immutable types:

private fun updatePath(paths: Map<String, Int>,
                       entry: Map.Entry<String, Int>,
                        node: String): Map<String, Int> {               (1)
  val currentDistance = paths.getOrDefault(entry.key, Integer.MAX_VALUE)
  val newDistance = entry.value + paths.getOrDefault(node, 0)
  return if (newDistance < currentDistance)
    paths + (entry.key to newDistance)                                  (2)
  else
    paths                                                               (2)
}
1The function’s signature only uses immutable types
2Because maps are immutable, they can be composed using the + operator. This returns a new map instance, which entries are the entries of both composed maps

The final step is to remove mutability from the implementation of updatePaths() now that it’s become easier to understand. For that, the forEach() that works on mutable state can be migrated to a sequence of transformations:

private fun updatePaths(node: String, paths: Map<String, Int>) =
  (weightedPaths[node]
    ?.map { updatePath(paths, it, node) }            (1)
    ?.fold(emptyMap()) { acc, item -> acc + item }   (2)
    ?: emptyMap<String, Int>())                      (3)
    - node
1The first transform is to map the Map item to another Map item using the updatePath() function
2Collect all Map entries into a single Map
3Return an empty Map if weightedPaths[node] is null. That makes the type of the evaluated expression a non-nullable Map, which can then be composed. Otherwise, we wouldn’t be able to compile the next line as - cannot be called on a nullable type

At that point, the source code has all features of Functional Programming: immutability and recursion.

Conclusion

Migrating from imperative to functional is mainly based on:

  • replacing loops by recursion
  • moving mutable state to accumulator parameters and return values

Baby steps help a lot when one is not used to Functional Programming.

The complete source code for this post can be found on Github.
Nicolas Fränkel

Nicolas Fränkel

Nicolas Fränkel is a Developer Advocate with 15+ years experience consulting for many different customers, in a wide range of contexts (such as telecoms, banking, insurances, large retail and public sector). Usually working on Java/Java EE and Spring technologies, but with focused interests like Rich Internet Applications, Testing, CI/CD and DevOps. Currently working for Hazelcast. Also double as a teacher in universities and higher education schools, a trainer and triples as a book author.

Read More