Dijkstra in a 2D Grid

Sep 1

We've now spent the last few articles looking at implementations of Dijkstra's algorithm in Haskell, with an emphasis on how to generalize the algorithm so it works for different graph types. Here's a quick summary in case you'd like to revisit some of this code, (since this article depends on these implementations).

Generalized Dijkstra Example

But now that we have a couple different examples of how we can generalize this algorithm, it's useful to actually see this generalization in action! Recall that our original implementation could only work with this narrowly defined Graph type:

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

We could add type parameters to make this slightly more general, but the structure remains the same.

newtype Graph node cost = Graph
   { edges :: HashMap node [(node, cost)] }

Suppose instead of this kind of explicit graph structure, we had a different kind of graph. Suppose we had a 2D grid of numbers to move through, and the "cost" of moving through each "node" was simply the value at that index in the grid. For example, we could have a grid like this:

[ [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]
  ]

The lowest cost path through this grid uses the following cells, for a total cost of 14:

[ [0, 2, 1, 3, x]
  , [x, x, x, 1, 4]
  , [x, x, x, x, 1]
  , [x, x, x, x, 1]
  , [x, x, x, x, 1]
  ]

We can make a "graph" type out of this grid in Haskell with a newtype wrapper over an Array. The index of our array will be a tuple of 2 integers, indicating row and column.

import qualified Data.Array as A

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

For simplicity, we'll assume that our array starts at (0, 0).

Getting the "Edges"

Because we now have the notion of a DijkstraGraph, all we need to do for this type to make it eligible for our shortest path function is make an instance of the class. The tricky part of this is the function for dijkstraEdges.

We'll start with a more generic function to get the "neighbors" of a cell in a 2D grid. Most cells will have 4 neighbors. But cells along the edge will have 3, and those in the corner will only have 2. We start such a function by defining our type signature and the bounds of the array.

getNeighbors :: A.Array (Int, Int) Int -> (Int, Int) -> [(Int, Int)]
getNieghbors input (row, col) = ...
  where
    (maxRow, maxCol) = snd . A.bounds $ input
    ...

Now we calculate the Maybe for a cell in each direction. We compare against the possible bounds in that direction and return Nothing if it's out of bounds.

getNeighbors :: A.Array (Int, Int) Int -> (Int, Int) -> [(Int, Int)]
getNeighbors input (row, col) = ...
  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

And as a last step, we use catMaybes to get all the "valid" neighbors.

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

Writing Class Instances

With this function, it becomes very easy to fill in our class instances! Let's start with the Multi-param class. We have to start by specifying the node type, and the cost type. As usual, our cost is a simple Int. But the node in this case is the index of our array - a tuple.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}

instance DijkstraGraph Graph2D (Int, Int) Int where
  ...

To complete the instance, we get our neighbors and combine them with the distance, which is calculated strictly from accessing the array at the index.

instance DijkstraGraph Graph2D (Int, Int) Int where
  dijkstraEdges (Graph2D arr) cell = [(n, arr A.! n) | n <- neighbors]
    where
      neighbors = getNeighbors arr cell

Now we can find the shortest distance! As before though, we have to be more explicit with certain types, as inference doesn't seem to work as well with these multi-param typeclasses.

dijkstraInput2D :: Graph2D
dijkstraInput2D = 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
  ]

-- Dist 14
cost2 :: Distance Int
cost2 = findShortestDistance dijkstraInput2D (0 :: Int, 0 :: Int) (4, 4)

Type Family Instance

Filling in the type family version is essentially the same. All that's different is listing the node and cost types inside the definition instead of using separate parameters.

{-# LANGUAGE TypeFamilies #-}

instance DijkstraGraph Graph2D where
  type DijkstraNode Graph2D = (Int, Int)
  type DijkstraCost Graph2D = Int
  dijkstraEdges (Graph2D arr) cell = [(n, arr A.! n) | n <- neighbors]
    where
      neighbors = getNeighbors arr cell

And calling our shortest path function works here as well, this time without needing extra type specifications.

dijkstraInput2D :: Graph2D
dijkstraInput2D = 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
  ]

-- Dist 14
cost3 :: Distance Int
cost3 = findShortestDistance dijkstraInput2D (0, 0) (4, 4)

Conclusion

Next time, we'll look at an even more complicated example for this problem. In the meantime, make sure you subscribe to our mailing list so you can stay up to date with the latest news!

As usual, the full code is in the appendix below. Note though that it depends on code from our previous parts: Dijkstra 2 (the Multi-param typeclass implementation) and Dijkstra 3, the version with a type family.

For the next part of this series, we'll compare this implementation with an existing library function!

Appendix

You can also find this code right here on GitHub.

{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeFamilies #-}

module Graph2D where

import qualified Data.Array as A
import Data.Maybe (catMaybes)

import qualified Dijkstra2 as D2
import qualified Dijkstra3 as D3

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

instance D2.DijkstraGraph Graph2D (Int, Int) Int where
  dijkstraEdges (Graph2D arr) cell = [(n, arr A.! n) | n <- neighbors]
    where
      neighbors = getNeighbors arr cell

instance D3.DijkstraGraph Graph2D where
  type DijkstraNode Graph2D = (Int, Int)
  type DijkstraCost Graph2D = Int
  dijkstraEdges (Graph2D arr) cell = [(n, arr A.! n) | n <- neighbors]
    where
      neighbors = getNeighbors arr cell

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

dijkstraInput2D :: Graph2D
dijkstraInput2D = 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
  ]

cost2 :: D2.Distance Int
cost2 = D2.findShortestDistance dijkstraInput2D (0 :: Int, 0 :: Int) (4, 4)

cost3 :: D3.Distance Int
cost3 = D3.findShortestDistance dijkstraInput2D (0, 0) (4, 4)

In Depth

James Bowen

Dijkstra in a 2D Grid

Simple Implementation

Generalized with a Multi-param Typeclass

Generalized with a Type Family