Adding BFS to Algebra.Graph.AdjacencyMap*.Algorithm

[TheChouzanOne]

I've noticed that there is no BFS implementation for adjacency maps but DFS does have one. It might be useful to have a single source shortest path algorithms for unlabelled graphs.

I've written a small blog/tutorial for my first implementation. It can be found here.

Its type currently is

bfsTree :: Ord a => a -> AdjacencyMap a -> AdjacencyMap a

It takes a root vertex, an AM and returns another AM. The problem is that the API is not similar to DFS, as its type shows:

dfsForest :: Ord a => AdjacencyMap a -> Forest a

My algorithm could be modified slightly to return a Tree a instead of an AM and then the new function

bfsForest :: Ord a => AdjacencyMap a -> Forest a

can be easily implemented using bfsTree as its foundation. Not sure if that would be enough though.

[TheChouzanOne]

Update: I found a possible problem with my BFS implementation. I am renaming bfsTree to bfsTreeAdjacencyMap and building a new function bfsTree that uses the previous one. The thing is that with the first one I could return an empty graph if the root vertex did not exist, but Tree does not have a way to represent an empty tree.

So, I am unsure on how could I proceed to fix this discrepancy, as using a Maybe return type would mean that the user could produce wrong Trees.

[snowleopard]

@TheChouzanOne Thanks, adding an implementation of the BFS algorithm would be great!

I suggest that as a first try you copy the existing API of DFS exactly -- note that it also needs to return the empty forest when given a nonexistent vertex. Let's see how it works out and adapt it if need be.

[TheChouzanOne]

@snowleopard I'm on it. I've already implemented a correct bfsForest, if you want to check it out (it's in the UpdatingBFS branch). I believe the implementation is a little messy and could be improve, but for the first try, it works!

Also, just to be clear, by "copy the existing API of DFS exactly" do you mean to have the same three functions

dfsForestFrom :: Ord a => [a] -> AdjacencyMap a -> Forest a
dfs :: Ord a => [a] -> AdjacencyMap a -> [a]
dfsForest :: Ord a => AdjacencyMap a -> Forest a

but for BFS?

bfsForestFrom :: Ord a => [a] -> AdjacencyMap a -> Forest a 
bfs :: Ord a => [a] -> AdjacencyMap a -> [a]
bfsForest :: Ord a => AdjacencyMap a -> Forest a -- Done! :)

[TheChouzanOne]

I've coded a cleaner and working version for bfsForest.

Also, I wrote a post about its development if you want to read it.

I still don't know if you would like to have all three functions (bfs, bfsForest and bfsForestFrom) or if bfsForest is enough, though.

[snowleopard]

@TheChouzanOne Thanks! For an initial prototype I suggest to implement the following two functions. We might rename them later, and in fact I think we might also rename some DFS functions to get to a more clear naming scheme.

-- Run BFS from the list of initial vertices, returning the resulting BFS forest.
bfsForestFrom :: Ord a => [a] -> AdjacencyMap a -> Forest a

-- Run BFS from the list of initial vertices (roots), returning the resulting list of 
-- levels, i.e. vertices that are at the same distance from the roots.
bfs :: Ord a => [a] -> AdjacencyMap a -> [[a]]

What is currently missing from your blog post and implementation is a good list of examples, like here, and complexity analysis.

Feel free to open a draft PR so we can start discussing specific details of the implementation.

[TheChouzanOne]

@snowleopard Sounds good! I'll be working on it then.