Boost logo

Boost :

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 (
>>> ).
>>> 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

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at