Re: [Boost-users] Details of boost parallel graph implementation

Subject: Re: [Boost-users] Details of boost parallel graph implementation
From: Marcin Zalewski (marcin.zalewski_at_[hidden])
Date: 2015-07-30 00:32:57

On Wed, Jul 29, 2015 at 4:26 AM Mayank Bakshi <mayank.bakshi_at_[hidden]> 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.