Purely Functional: Graph Search Algorithms

Graph search algorithms solve the following general problem:

Suppose you have a graph, and you begin at some node on the graph. This graph, for example, could represent a map of New York City — the edges could be streets, nodes could be intersections of streets, and the starting node could be your current location. The problem is to find a path with some property that ends at some goal node. On the graph of New York City, you might want to find the shortest route to a bar. On a graph of a game of chess (where nodes are game states and edges are moves), you might want to find any way for you to win. For our purposes, we will assume that the graph is connected, meaning there exists a path between every pair of nodes.

For now, we will consider two graph search algorithms: depth-first and breadth-first search. Depth-first search (DFS) simply finds any path from the start node to a goal node, and breadth-first search finds the shortest path. DFS search simply starts at the starting node and takes an edge over and over again until it reaches a goal node. Sometimes, if it reaches a situation where it can not reach any other node from where it is and has still not reached a goal node, it will backtrack up one level and try again with another node. If the graph is infinitely large, then DFS may go on forever.

Breadth-first search (BFS) takes it a different strategy: from the starting node, it iteratively expands a “search bubble” — all nodes within this bubble will be at most a certain distance away. It then looks for a goal node within this bubble. If it does not find one, then it expands the bubble. Even if the graph is infinitely large, it will find a goal node if it exists, and it will find the shortest path to it.

We should first think about how we can represent a graph. The important thing about a graph is that each node consists of some unique “label” and a list of “connections” to other nodes. Furthermore, if we have information about just a single node in the graph, we can recover the entire graph by just following the connections of each node to the the next node. If we do this process enough time (until we start visiting the same node twice), we can determine what the entire graph looks like. Therefore, we only need to have the representation of a single node (the node’s label and its connections), and the entire graph can be reconstructed automatically. We will call the node we choose to represent the entire graph with the “focus” of the graph. In Haskell, we can represent a graph the following way:

data Graph a = Node { label :: a, connections :: [Graph a] } 

Therefore, we can represent a simple cyclic graph with 5 vertices the following way:

cycle5 :: Graph Int
cycle5 = Node 1 [Node 2 [Node 3 [Node 4 [Node 5 [cycle5]]]]]

Note how, just like lists and trees, graphs in Haskell are defined recursively. This means that if we were to traverse this graph using some search procedure, we would keep cycling from 1 to 5.

It is often useful to prune the graph into a search tree so as to remove any cycles. In other words, we can transform cycle5 into the following:

pruned_cycle5 :: Graph Int
pruned_cycle5 = Node 1 [Node 2 [Node 3 [Node 4 [Node 5 [Node 1 []]]]]]

And it will be understood that the node labeled 1 later in the graph is the same as the node labeled 1 that is the focus of the graph. Pruning turns the infinitely large, recursively defined representation of the graph into an only finitely large representation that can be used to reconstruct that very same graph. We can define the pruning function in the following way:

prune :: Eq a => Graph a -> Graph a
prune g = prune' [] g
    where
        prune' ps (Node x xs) = if x `elem` ps
            then Node x []
            else Node x (map (prune' (x:ps)) xs) 

The prune function will traverse the graph by following connections and maintaining a list of node labels it has seen so far — if it encounters a node it has seen before, it won’t expand its connections. Pruning is useful in both DFS and in BFS. Without pruning, DFS may not terminate (if it encounters a cycle in the graph). Although BFS will always terminate, pruning speeds it up by eliminating cycles in the graph. This does not change the result of the BFS because the shortest path can never contain cycles — if it did, then we could always cut the cycle out of the “shortest” path, and we would get a shorter path. We will always prune the graph before feeding it into a search algorithm.

The easier search algorithm to implement is DFS because we only need to find a single path to a goal node, not necessarily the shortest one. In Python, DFS would be implemented with a stack like so (assuming the graph has already been pruned):

def dfs(isGoal, startNode):
    stack = [[startNode]]
    while len(stack) != 0:
        path = stack.pop()
        if isGoal(path[-1]):
            return path
        else:
            for child in path[-1].connections():
                stack.append(path + [child])
    return None 

Because we are using a stack, a last-in-first-out (LIFO) data structure, we always pop out the last path we extended. If we end up at a dead-end, we always end up popping out the last path we evaluated, which enables backtracking. In Haskell, we don’t need a separate stack to store all the paths — we can use recursion, which is essentially using the call stack as our LIFO structure. Here’s how we can do it:

dfs :: (a -> Bool) -> Graph a -> Maybe [a]
dfs p (Node x xs) = if p x
    then Just [x]
    else fmap (x:) . msum . map (dfs p) $ xs 

First, let’s inspect the type signature and convince ourselves it’s the same as the Python program. The first argument is the “isGoal” parameter, which is a function that takes in a node label as an argument and returns a Boolean indicating whether or not it qualifies as a goal node. The second argument is a graph, with the starting node as its focus. The dfs function can either output a list of node labels representing a path from the starting node to a goal node wrapped in a Just constructor, or it can output a Nothing, indicating that there is no path from the starting node to a goal node. p is the goal predicate, x is the label of the node in focus, and xs is the list of connections for that node (recall that it is of type [Graph a]).

The first part of the if-branch is relatively simple: if the currently focused node, x, satisfies the goal predicate, then the path to a goal is Just [x] — that is, we’re already at a goal node. To understand the second part, let’s first try to understand its components:

  1.  map (dfs p) takes a list of graphs and runs the same DFS procedure on all of them, with the same goal predicate. It will output a list of Maybe [a]s.
  2. msum takes a list of Maybe t values and returns the first one that is not Nothing. The “m” in msum :: Monad m => [m a] -> m a refers to “Monad”, in this case the Maybe monad. We can think of Nothing as a sort of “zero” element, and we are summing up all the Maybe t values in a list. Because zero is the identity for addition, it will be ignored in msum and we will, by convention, return the first Just value.
  3. fmap (x:) appends x to the beginning of the list inside a Just. Functor f => fmap :: (a -> b) -> (f a -> f b) is a “lifting” operation for functors, which are generally containers for elements. In this case, our functor is Maybe. As an example:
    (+1) :: Int -> Int
    fmap (+1) :: Maybe Int -> Maybe Int
    fmap (+1) (Just 3) = Just 4
    fmap (+1) Nothing = Nothing
    fmap (1:) (Just [2, 3, 4]) = Just [1, 2, 3, 4]
    fmap (1:) Nothing = Nothing 

    Note that fmap will return Nothing if you try to operate on Nothing.

Putting this all together, if x does not satisfy the goal predicate, then it will run the dfs p function on all the connections of the focused node, it will find the first one that succeeds in finding a goal node, and it will append x to the beginning of that path because x had to be visited before traversing that path. If DFS fails to find a goal node on all of the connections, then because fmap f Nothing = Nothing for all f, Nothing will be returned. Furthermore, msum [] = Nothing (intuitively, the sum of zero number of things is zero), and so if a node does not satisfy the goal predicate and it has no connections, then Nothing will be returned, as we expect. In all cases, therefore, this dfs function is correct.

However, it looks like this implementation of DFS is run on every single connection of a single node, whereas DFS should only run along a single path and backtrack only when necessary. However, thanks to laziness, that is not the case. msum will only have to evaluate the contents of the list map (dfs p) xs until it finds the first successful path, and DFS will not be run on the remainder of the list. Backtracking is not as explicit in this implementation, but it occurs when msum encounters a Nothing in the list and ignores it and moves on to the next element.

We can confirm that the entire graph is not being searched by using one of the tools in the Haskell toolbox, the :sp directive in GHCi. It will show you how a given variable is currently represented in memory: which portions are thunks and which portions have been evaluated. For example, if we define:

let x = 1 : 2 : 3 : 4 : [] 

Then:

GHCi> :sp x
====> x = _ 

Which indicates that because of lazy evaluation, x is entirely a thunk. Now, if we evaluate the head of x:

GHCi> head x
====> 1
GHCi> :sp x
====> x = 1 : _ 

Which indicates that only the portion of x that has been evaluated is the head, and the tail is still a thunk. We can use :sp to determine which portions of a data structure a function evaluates — in this case, which nodes in a graph our DFS procedure touches. Let’s try it out:

GHCi> let g = Node 1 [Node 2 [Node 3 []], Node 4 [Node 5 []], Node 5 []]
GHCi> let pg = prune g
GHCi> :sp pg
====> pg = _
GHCi> dfs (== 5) pg
====> Just [1, 4, 5]
GHCi> :sp pg
====> pg = Node 1 (Node 2 [Node 3 []] : Node 4 (Node 5 _ : _) : _) 

Clearly, it does not have to process the entire search tree — once it finds a path to 5, it stops and returns that path.

BFS is a bit more difficult to tackle. But first, let’s discuss how we would implement BFS in Python:

def bfs(isGoal, startNode):
    queue = [[startNode]]
    while len(queue) != 0:
        path = queue.pop(0)
        if isGoal(path[-1]):
            return path
        else:
            for child in path[-1].connections():
                queue.append(path + [child])
    return None 

The only difference is that instead of a stack, we have a first-in-first-out (FIFO) queue! The basic idea is to preserve the invariant that in each iteration, we always pop the shortest path out of the queue. This is because every time we extend a path, we add it to the end of the queue, and we always pop from the front, selecting the paths that haven’t been extended yet.

In Haskell, however, the implementation for DFS and BFS aren’t quite so similar. What complicates things is that while stacks can be implemented easily using ordinary recursion, queues don’t have a simple analogue. We would like to avoid using an extra data structure, if possible, and stick to recursion.

Recall that BFS accomplishes two things: it finds the shortest path to a goal node, and it does not touch any part of the graph outside the search bubble. Therefore, if we find that the shortest path to a goal node is 3 steps long, then all nodes that are more than 3 steps away from the starting node should remain untouched after the algorithm terminates.

First, let’s suppose we had a function, rankedPaths, which would take in a graph and output a list of all paths from the focus of the graph to every other node in order of increasing length. For now, we can simply leave this as undefined:

rankedPaths :: Graph a -> [[a]]
rankedPaths g = undefined 

Leaving it as undefined for now allows us to specify a type for rankedPaths without having to implement it, so that we can specify how it will interlock with other functions but put off actually writing the function for later.

We also have a function in the Data.List module called find :: (a -> Bool) -> [a] -> Maybe a which will find the first element in a list that satisfies a given predicate. If it finds it, it will return that element wrapped in a Just constructor; if it does not, it will return Nothing. Finally, we also have a function called last :: [a] -> a that will return the last element of a list. How can we put these together to implement BFS?

What we want to do is implement a function bfs :: (a -> Bool) -> Graph a -> Maybe a that will first generate a list of all paths in order of increasing length, and then select the first path whose last node satisfies our goal test. The following code does just that:

bfs :: (a -> Bool) -> Graph a -> Maybe a
bfs p = find (p . last) . rankedPaths 

However, we need to make sure that rankedPaths is evaluated lazily — find will stop as soon as it finds an element that satisfies the given predicate, but we need to make sure that evaluating the first element of the list does not force evaluation of the entire list. We want only the nodes inside the search bubble to be touched.

To implement rankedPaths, we have to ensure that evaluating a given element of the list will not force the evaluation of any elements that come afterwards — we will do so by defining the tail of the returned list recursively and the head normally. First, note that if our graph is Node x xs (recall x will pattern-match as the label of the node currently in focus, and xs will pattern-match as the list of connections of this node), then the shortest path in this graph is [x], which is just a path starting and ending at x. The next shortest paths would be the paths from x to its connections, and then the paths from x to the connections of its connections, and so on.

So now we’ve learned a bit more about what rankedPaths should look like:

rankedPaths :: Graph a -> [[a]]
rankedPaths (Node x xs) = [x] : undefined 

Next comes the induction step: suppose we knew what map rankedPaths xs, or rankedPaths for every connection of the currently focused node, was. Can we combine this data to get rankedPaths for the currently focused node? If we have ranked lists of paths for all the connections of a node, can we combine them into a single ranked list of paths for the node?

We can, if we imagine we had a function called mergeRanked :: [[a]] -> [[a]] -> [[a]]. This function will take two ranked lists of paths, and merge them into a single ranked list of paths. Then, we can use foldr mergeRanked to merge a list of ranked lists of paths into a single ranked list of paths, and append an x to the beginning of each path using map (x:) . Finally, we also have to consider the case of the single path beginning and ending at x, so we append the path [x] to the beginning of the entire resulting list. The following is how we can implement rankedPaths:

rankedPaths :: Graph a -> [[a]]
rankedPaths (Node x xs) = ([x]:) . map (x:) . foldr mergeRanked [] . map rankedPaths $ xs 

Of course, we still have to implement mergeRanked. The basic idea is similar to how we implement the merge process in merge sort — we repeatedly take the smaller of the two heads from the two lists until one of the lists is empty:

mergeRanked :: [[a]] -> [[a]] -> [[a]]
mergeRanked [] ys = ys
mergeRanked xs [] = xs
mergeRanked (x:xs) (y:ys) = if length x < length y
    then x : (mergeRanked xs (y:ys))
    else y : (mergeRanked (x:xs) ys) 

Altogether, we have:

bfs :: (a -> Bool) -> Graph a -> Maybe [a]
bfs p = find (p . last) . rankedPaths
    where
        rankedPaths :: Graph a -> [[a]]
        rankedPaths (Node x xs) = ([x]:) . map (x:) . foldr mergeRanked [] . map rankedPaths $ xs
        
        mergeRanked :: [[a]] -> [[a]] -> [[a]]
        mergeRanked [] ys = ys
        mergeRanked xs [] = xs
        mergeRanked (x:xs) (y:ys) = if length x < length y
            then x : (mergeRanked xs (y:ys))
            else y : (mergeRanked (x:xs) ys) 

And that’s the implementation of BFS! Side-by-side with the python implementation, it isn’t quite as terse, but it is idiomatically using recursion and laziness to our advantage. We can ensure that BFS is actually lazy and doesn’t touch anything outside the search bubble by using the :sp tool again:

GHCi> let g = Node 1 [Node 2 [Node 3 []], Node 4 [Node 5 []], Node 5 []]
GHCi> let pg = prune g
GHCi> :sp pg
====> pg = _
GHCi> bfs (== 5) pg
====> Just [1, 5]
GHCi> :sp pg
====> pg = Node 1 [Node 2 [Node 3 _], Node 4 _, Node 5 _] 

And indeed, nothing outside of 1 step beyond our search bubble has been touched.

Please leave comments below and let me know if you have any corrections or need any clarifications.

Advertisements

3 thoughts on “Purely Functional: Graph Search Algorithms

  1. “Furthermore, if we have information about just a single node in the graph, we can recover the entire graph by just following the connections of each node to the the next node.”
    So long as it is connected (which the usual definition of a graph does not necessitate).

    Like

  2. Thanks for the post. It would be interesting to also see some performance figures. I remember being quite frustrated about poor performance of my Dijkstra code in Haskell (finding shortest paths is more difficult, of course, and perhaps worth another post?).

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s