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: 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