Dijkstra Comparison: Looking at the Library Function

Sep 5

In the last few articles I've gone through my approach for generalizing Dijkstra's algorithm in Haskell. The previous parts of this included:

But of course I wasn't the first person to think about coming up with a general form of Dijkstra's algorithm in Haskell. Today, we'll look at the API for a library implementation of this algorithm and compare it to the implementations I thought up.

Comparing Types

So let's look at the type signature for the library version of Dijkstra's algorithm.

dijkstra ::
    (Foldable f, Num cost, Ord cost, Ord State)
  => (state -> f state) -- Function to generate list of neighbors
  -> (state -> state -> cost) -- Function for cost generation
  -> (state -> Bool) -- Destination predicate
  -> state -- Initial state
  -> Maybe (cost, [state]) -- Solution cost and path, Nothing if goal is unreachable

We'd like to compare this against the implementations in this series, but it's also useful to think about the second version of this function from the library: dijkstraAssoc. This version combines the functions for generating neighbors and costs:

dijkstraAssoc ::
    (Num cost, Ord cost, Ord state)
  => (state -> [(state, cost)])
  -> (state -> Bool)
  -> state
  -> Maybe (cost, [state])

And now here's the signature for the Multi-Param typeclass version I wrote:

findShortestDistance ::
    (Hashable node, Eq node, Num cost, Ord cost, DijkstraGraph graph)
  => graph -> node -> node -> Distance cost

We can start the comparison by pointing out a few surface-level differences..

First, the library uses Nothing to represent a failure to reach the destination, instead of a Distance type with Infinity. This is a sensible choice to spare API users from incorporating an internal type into their own code. However, it does make some of the internal code more cumbersome.

Second, the library function also includes the full path in its result which is, of course, very helpful most of the time. The implementation details for this aren't too complicated, but it requires tracking an extra structure, so I have omitted it so far in this series.

Third, the library function takes a predicate for its goal, instead of relying on an equality. This helps a lot with situations where you might have many potential destinations.

Functional vs. Object Oriented Design

But the main structural difference between our functions is, of course, the complete lack of a "graph" type in the library implementation! Our version provides the graph object and adds a typeclass constraint so that we can get the neighboring edges. The library version just includes this function as a separate argument to the main function.

Without meaning to, I created an implementation that is more "object oriented". That is, it is oriented around the "object" of the graph. The library implementation is more "functional" in that it relies on passing important information as higher order functions, rather than associating the function specifically with the graph object.

Clearly the library implementation is more in keeping with Haskell's functional nature. Perhaps my mind gravitated towards an object oriented approach because my day job involves C++ and Python.

But the advantages of the functional approach are clear. It's much easier to generalize an algorithm in terms of functions, rather than with objects. By removing the object from the equation entirely, it's one less item that needs to have a parameterized (or templated) type in our final solution.

However, this only works well when functions are first class items that we can pass as input parameters. Languages like C++ and Java have been moving in the direction of making this easier, but the syntax is not nearly as clean as Haskell's.

Partial function application also makes this a lot easier. If we have a function that is written in terms of our graph type, we can still use this with the library function (see the examples below!). It is most convenient if the graph is our first argument, and then we can partially apply the function and get the right input for, say, dijkstraAssoc.

Applying The Library Function

To close this article, let's see these library functions in action with our two basic examples. Recall our original graph type:

import Data.HashMap.Strict (HashMap)
import qualified Data.HashMap.Strict as HM

data Distance a = Dist a | Infinity
  deriving (Show, Eq)

newtype Graph = Graph
   { edges :: HashMap String [(String, Int)] }

graph1 :: Graph
graph1 = Graph $ HM.fromList
  [ ("A", [("D", 100), ("B", 1), ("C", 20)])
  , ("B", [("D", 50)])
  , ("C", [("D", 20)])
  , ("D", [])
  ]

To fill in our findShortestDistance function, we can easily use dijkstraAssoc, using the edges field of our object to supply the assoc function.

import Algorithm.Search (dijkstraAssoc)
import Data.Maybe (fromMaybe)

findShortestDistance :: Graph -> String -> String -> Distance Int
findShortestDistance graph start end = case answer of
  Just (dist, path) -> Dist dist
  Nothing -> Infinity
  where
    costFunction node = fromMaybe [] (HM.lookup node (edges graph))
    answer = dijkstraAssoc costFunction (== end) start

...

>> findShortestDistance graph1 "A" "D"
Distance 40

But of course, we can also just skip our in-between function and use the full output of the library function. This is a little more cumbersome in our case, but it still works.

>> let costFunction node = fromMaybe [] (HM.lookup node (edges graph1))
>> dikjstraAssoc costFunction (== "D") "A"
Just (40, ["C", "D"]

Notice that the library function omits the initial state when providing the final path.

Graph 2D Example

Now let's apply it to our 2D graph example as well. This time it's easier to use the original dijkstra function, rather than the version with "assoc" pairs.

import qualified Data.Array as A

newtype Graph2D = Graph2D (A.Array (Int, Int) Int)

getNeighbors :: A.Array (Int, Int) Int -> (Int, Int) -> [(Int, Int)]
getNeighbors input (row, col) = catMaybes [maybeUp, maybeDown, maybeLeft, maybeRight]
  where
    (maxRow, maxCol) = snd . A.bounds $ input
    maybeUp = if row > 0 then Just (row - 1, col) else Nothing
    maybeDown = if row < maxRow then Just (row + 1, col) else Nothing
    maybeLeft = if col > 0 then Just (row, col - 1) else Nothing
    maybeRight = if col < maxCol then Just (row, col + 1) else Nothing

graph2d :: Graph2D
graph2d = Graph2D $ A.listArray ((0, 0), (4, 4))
  [ 0, 2, 1, 3, 2
  , 1, 1, 8, 1, 4
  , 1, 8, 8, 8, 1
  , 1, 9, 9, 9, 1
  , 1, 4, 1, 9, 1
  ]

findShortestPath2D :: Graph2D -> (Int, Int) -> (Int, Int) -> Maybe (Int, [(Int, Int)])
findShortestPath2D (Graph2D graph) start end = dijkstra
  (getNeighbors graph)
  (\_ b -> graph A.! b)
  (== end)
  start

...

>> findShortestDistance2D graph2d (0, 0) (4, 4)
Just (14, [(0, 1), (0, 2), (0, 3), (1, 3), (1, 4), (2, 4), (3, 4), (4, 4)]

Conclusion

In the final part of this series we'll consider the "monadic" versions of these library functions and why someone would want to use them.

If you enjoyed this article, make sure to subscribe to our mailing list! This will keep you up to date on all the latest news about the site, as well as giving you access to our subscriber resources that will help you on your Haskell journey!

As always, you can find the full code implementation for this article on GitHub. But it is also given below in the appendix below.

Appendix - Full Code

module DijkstraLib where

import qualified Data.Array as A
import Data.HashMap.Strict (HashMap)
import qualified Data.HashMap.Strict as HM
import Data.Maybe (catMaybes, fromMaybe)
import Algorithm.Search (dijkstra, dijkstraAssoc)

data Distance a = Dist a | Infinity
  deriving (Show)

newtype Graph = Graph
   { edges :: HashMap String [(String, Int)] }

graph1 :: Graph
graph1 = Graph $ HM.fromList
  [ ("A", [("D", 100), ("B", 1), ("C", 20)])
  , ("B", [("D", 50)])
  , ("C", [("D", 20)])
  , ("D", [])
  ]

findShortestDistance :: Graph -> String -> String -> Distance Int
findShortestDistance graph start end = case answer of
  Just (dist, path) -> Dist dist
  Nothing -> Infinity
  where
    costFunction node = fromMaybe [] (HM.lookup node (edges graph))
    answer = dijkstraAssoc costFunction (== end) start

newtype Graph2D = Graph2D (A.Array (Int, Int) Int)

getNeighbors :: A.Array (Int, Int) Int -> (Int, Int) -> [(Int, Int)]
getNeighbors input (row, col) = catMaybes [maybeUp, maybeDown, maybeLeft, maybeRight]
  where
    (maxRow, maxCol) = snd . A.bounds $ input
    maybeUp = if row > 0 then Just (row - 1, col) else Nothing
    maybeDown = if row < maxRow then Just (row + 1, col) else Nothing
    maybeLeft = if col > 0 then Just (row, col - 1) else Nothing
    maybeRight = if col < maxCol then Just (row, col + 1) else Nothing

graph2d :: Graph2D
graph2d = Graph2D $ A.listArray ((0, 0), (4, 4))
  [ 0, 2, 1, 3, 2
  , 1, 1, 8, 1, 4
  , 1, 8, 8, 8, 1
  , 1, 9, 9, 9, 1
  , 1, 4, 1, 9, 1
  ]

findShortestPath2D :: Graph2D -> (Int, Int) -> (Int, Int) -> Maybe (Int, [(Int, Int)])
findShortestPath2D (Graph2D graph) start end = dijkstra
  (getNeighbors graph)
  (\_ b -> graph A.! b)
  (== end)
  start

In Depth

James Bowen