Dijkstra in a 2D Grid
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).
Simple Implementation
Generalized with a Multi-param Typeclass
Generalized with a Type Family
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)