On Wed, Jul 29, 2015 at 4:26 AM Mayank Bakshi <mayank.bakshi@tcs.com> wrote:

Hello,

I am working on mpi implementation of boost for breadth first search.
What is the algorithmic detail for BFS in boost.mpi? How the graph is processed by each rank which we provide in mpirun (load distribution among different processes)?

The sequential BGL library is overloaded on distributed graphs:

https://github.com/boostorg/graph/blob/master/include/boost/graph/breadth_first_search.hpp

Look for the mpl::true_ and mpl::bool_ to see where distributed vs. not-distributed selection is made. graph_parallel provides some additional overloads of the helper, but it does not define a brand new BFS:

https://github.com/boostorg/graph_parallel/blob/master/include/boost/graph/distributed/breadth_first_search.hpp

The whole magic happens in the queue, graph, and property maps data structures. The queue distributes work, and it also implements a global "empty" check, and the property maps allow accessing remote vertices. So, if you need MPI BFS, one is already there.