Re: [boost] [BGL] Trying to get a correclty working Parallel BFS code

Subject: Re: [boost] [BGL] Trying to get a correclty working Parallel BFS code
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-10-27 13:27:31

On Tue, 27 Oct 2009, Sandeep Gupta wrote:

> On Mon, Oct 26, 2009 at 11:29 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:
>
>> On Mon, 26 Oct 2009, Sandeep Gupta wrote:
>>
>>  Hi All,
>>>  I  have spent significant effort on parallel bfs. Currently its almost
>>> working. I would really appreciate some help to get it running correctly.
>>> I
>>> have attached the code (self contained and requires no input file).
>>> I think I have followed all the guidelines regarding distributed property
>>> maps mentioned in the docs (
>>>
>>> http://www.osl.iu.edu/research/pbgl/documentation/graph/breadth_first_search.html
>>> ).
>>> I am out of ideas of where things can could have gone wrong.
>>>
>>
>> The graph is distributed by source vertex across all processors, and so you
>> need to add them on every processor (or at least on the processor that owns
>> them, which is probably not processor 0).  Thus, your graph is missing
>> whichever edges would be on processor 1, leading to incorrect results.  Try
>> adding all of the edges on all processors and see if this fixes your
>> problem.
>>
>> -- Jeremiah Willcock
>>
>>
>
> Jeremiah, thanks so much looking into this promptly. I took cues from
> building distributed graph section of distributed adjacency list page which
> has an example:
>
> ///---------------Begin example
>
> Graph g(n); // initialize with the total number of vertices, n
> if (process_id(g.process_group()) == 0) {
>  // Only process 0 loads the graph, which is distributed automatically
>  int source, target;
>  for (std::cin >> source >> target)
>    add_edge(vertex(source, g), vertex(target, g), g);
> }
>
> // All processes synchronize at this point, then the graph is complete
> synchronize(g.process_group());
> //---------End
>
> Looking at this, it seems that distribution happens automatically which is
> what the manual says.
> This is further confirmed when I output the subgraphs at each process.

OK.  I was mistaken on this point then.  Could you please try the 
following graph with a distribution that puts vertices 0-3 on rank 0 and 
4 on rank 1 (just add three dummy vertices on the end and use a block 
distribution)?

0 -> 1
1 -> 2
2 -> 3
0 -> 4
4 -> 3

See if the depths are reasonable for that graph.  Also, the contents of 
the predecessor maps output by your search (both the original one and the 
graph I just gave) would be nice too; that is just an extra map you can 
give to BFS and you can just dump it the same way you dump depth values.

-- Jeremiah Willcock