Adding BFS support to AdjacencyMaps.

[TheChouzanOne]

I've added a bfsForest algorithm that makes use of "helper" functions for a total of 4 new functions. These are located in AdjacencyMap/Algorithm.hs, however, I believe that the 3 helped functions might be rellocated to keep Algorithm.hs clean.

Complexity analysis is still missing.

Also, the next functions need to be implemented.

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

A link to posts regarding the development of this PR can be found here.

[TheChouzanOne]

I've started implementing the missing functions. bfsForestFrom seems to be ready, but I need to clarify bfs. To easily see the implementation please refer to this link.

By running bfs on a graph: a) do you want vertices that are on the same level but different trees to be included in the same list? Or b) should they be in different lists?

For example, let g = (1*2) + (3*4) + (5*6). Running bfs [1,2] g could return a) [[1,3],[2,4]] or b) [ [ [1],[2] ] , [ [3],[4] ] ]

The type signature indicates the option (a) is the correct one, but (b) splits the different trees generated, which would require [[[a]]] to be returned.

[snowleopard]

a) do you want vertices that are on the same level but different trees to be included in the same list?

Yes. The first element of the list contains the roots that are present in the graph, the second element contains all vertices reachable from roots in 1 step, etc.

For example, let g = (1*2) + (3*4) + (5*6). Running bfs [1,2] g could return a) [[1,3],[2,4]] or b) [ [ [1],[2] ] , [ [3],[4] ] ]

Neither a) not b) matches the desired output, which in this case should be just [[1,2]], because nothing else is reachable from the roots 1 and 2.

Another example with your graph: bfs [1,3] g == [[1,3], [2,4]].

[TheChouzanOne]

Another example with your graph: bfs [1,3] g == [[1,3], [2,4]].

There was an error with my example. bfs [1,3] g was what I meant. Thank you for the clarification.

[snowleopard]

@TheChouzanOne Thanks for adding complexity bounds. O(n^2 * log(n)) sounds too slow though! Can we get closer to linear O(n+m) or at least O((n+m)*log(n))?

[TheChouzanOne]

Can we get closer to linear O(n+m) or at least O((n+m)*log(n))?

I've just realized that my rough estimate was completely wrong and the real bound was O (n^2). Still, pretty slow. I've changed the implementation of bfsTreeAdjacencyMap to run in O (v + e * log(v) ) time now, much better.

That log (v) comes from the fact that Map.lookup runs in O (log(n)). If time complexity was constant, the algorithm could run in O(v+e), but I don't know which Haskell's data structure could help here.

Also, I added a new internal function to achieve less running time, which I've documented. I've been pretty busy and haven't been able to update my blog, but plan to do so with these last updates once I have time.

Anyways, what do you think about the current state of the code?

[TheChouzanOne]

Wait, I've just realized something and am confused. I am not sure if I am tired (it's 3 a.m.), but isn't O (v + e * log(v) ) not much of an improvement? Given a full graph, e=(v * (v-1)) /2 = O(v^2), so time complexity would be O (v^2 * log(v) ), which is worse than expected. Am I correct or tired?

[snowleopard]

but isn't O (v + e * log(v) ) not much of an improvement?

@TheChouzanOne This is a big improvement, because graphs are rarely fully connected! In the most typical case we have something like m = O(n).

Thanks for the revision, I'll take a look soon.

[snowleopard]

P.S.: I'm using n = |V| and m = |E|, as in the Alga documentation.

[TheChouzanOne]

I've changed documentation notation to n and m for vertices and edges, respectively.

[snowleopard]

@TheChouzanOne Thanks for the fixes!

At the moment the implementation looks unnecessarily complex to me. I don't understand why we need auxiliary functions like bfsTreeAdjacencyMap and others.

BFS is a very simple algorithm conceptually: you traverse all vertices starting with a root, marking each vertex with its parent. This information should be sufficient for extracting a tree for each root.

Furthermore, each example should have an associated test in the testsuite. You can have a look at how each example is tested by looking at the implementation of DFS.

[TheChouzanOne]

At the moment the implementation looks unnecessarily complex to me. I don't understand why we need auxiliary functions like bfsTreeAdjacencyMap and others.

I agree that implementation looks too complex. The reason I decided to use auxiliary functions like the one you mention was because I thought it owuld be easier to build an AdjacencyMap that represents a tree, and then parse it into an actual Tree type.

I will do some research on how this problem is normally solved with functional programming and rewrite the algorithms in a simpler manner. This might take some time given that I have many end of semester school projects at the moment.

Furthermore, each example should have an associated test in the testsuite. You can have a look at how each example is tested by looking at the implementation of DFS.

Sounds good. I'll look into it. Does this have something to do with Travis CI build failing? I don't really have much experience with continous integration software.

[snowleopard]

I will do some research on how this problem is normally solved with functional programming and rewrite the algorithms in a simpler manner. This might take some time given that I have many end of semester school projects at the moment.

@TheChouzanOne No problem, take your time. I'll ping you if this becomes more urgent.

Does this have something to do with Travis CI build failing? I don't really have much experience with continous integration software.

No, I don't think the testsuite is related to the CI failures. I've restarted Travis -- hopefully it will complete successully this time.