Subject: Re: [boost] [BGL] Trying to get a correclty working Parallel BFS code
From: Nick Edmonds (ngedmond_at_[hidden])
Date: 2009-11-11 12:22:34
On Nov 10, 2009, at 6:53 PM, Sandeep Gupta wrote:
> On Tue, Nov 10, 2009 at 2:51 PM, Nick Edmonds
> <ngedmond_at_[hidden]>wrote:
>
>> --snip-- (sorry, first reply was too big)
>>
>>
>>
>>>> Hi Nick,
>>>>
>>>> Thanks for the explanation of the distributed BFS. This is
>>>> indeed quite
>>> helpful. Especially at later stages. I haven't gotten to a point to
>>> comment
>>> on the data model but the current architecture is swell from what
>>> I can
>>> judge.
>>>
>>> I hesitate to ask explanation at every minor detail but I now
>>> confused
>>> about passing the same vertex descriptor. Specifically I didn't
>>> quite
>>> grasp
>>> the statement "source vertex just has to be
>>> graph_traits<Graph>::vertex_descriptor, which you can construct
>>> using
>>> vertex() call if you want to generate it from a global vertex
>>> index".
>>> The source vertex has to graph_traits<Graph>::vertex_descriptor
>>> which I
>>> takes two arguments the index and the graph --these two parameters
>>> can
>>> only
>>> identify local vertices. For global vertices we need global
>>> descriptors
>>> which also require the owner.
>>>
>>> Appreciate your help in clarifying this.
>>>
>>> Thanks
>>> Sandeep
>>>
>>
>> The vertex() call takes a global index and constructs a
>> vertex_descriptor,
>> which is basically a pair containing the local index and the owning
>> process.
>> vertex(i, g) will construct the i'th vertex descriptor in g on any
>> process,
>> regardless of where the vertex is actually stored. The confusion
>> is that
>> there are two indices here, global indices, and local indices. The
>> graph
>> distribution object maps between the two. vertex() takes a global
>> index,
>> specifically for this use case.
>>
>> Hope that helps,
>>
>>
>
>> Hi Nick,
>>
> Sorry, I didn't mean to imply that your first reply was too big. Your
> explanation of how the PBFS is actually working is indeed quite
> helpful.
> Just that rIght now I just too focussed on get the code working.
> Ofcourse,
> when I dig deeper I would certainly have to refer to your exposition.
>
> Right now in the code I am passing vertex(0,g) to all processes.
> This means, based upon the explanation, that we are performing BFS
> on all
> processes from the node with global identifier as 0. But still the
> code is
> not outputting right result. There is something more to it or I again
> misunderstood your explanation.
>
> Thanks for your patience.
>
> Sandeep
Hi Sandeep,
I didn't mean that you implied my reply was too big, this thread just
exceeded the 75k limit on messages so I trimmed it :)
How are you verifying your result? Try inserting:
BGL_FORALL_EDGES(e, g, Graph) {
request(distance, target(e, g)); // to fetch all the distances
where one endpoint of an edge is non-local
}
synchronize(distance); // deliver fetched distances
BGL_FORALL_EDGES(e, g, Graph) {
assert(get(distance, target(e, g)) <= get(distance, source(e, g)) +
1);
}
Let me know if that passes. Also, can you give me the type of
distributed_property_map? I'll also attach the version of your code I
cleaned up a while ago in case things haven't changed much and it's
still useful. This version of the code passes for me.
Cheers,
Nick