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: Sandeep Gupta (gupta.sandeep_at_[hidden])
Date: 2009-10-29 21:40:34

On Thu, Oct 29, 2009 at 1:12 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:

> On Thu, 29 Oct 2009, Sandeep Gupta wrote:
>
>  On Wed, Oct 28, 2009 at 5:49 PM, Sandeep Gupta <gupta.sandeep_at_[hidden]
>> >wrote:
>>
>>
>>>
>>> On Tue, Oct 27, 2009 at 9:31 PM, Jeremiah Willcock <jewillco_at_[hidden]
>>> >wrote:
>>>
>>>  On Tue, 27 Oct 2009, Sandeep Gupta wrote:
>>>>
>>>>  The error snippet regarding  predecessor map:
>>>>
>>>>>
>>>>>> error: no match for call to
>>>>>>
>>>>>>
>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&)'
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> ../../../boost/property_map/parallel/impl/distributed_property_map.ipp:141:
>>>>>> error: no match for call to
>>>>>>
>>>>>>
>>>>>> '(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::error_property_not_found>)
>>>>>> (const boost::detail::parallel::global_descriptor<unsigned int>&,
>>>>>> boost::detail::error_property_not_found&, const
>>>>>> boost::detail::error_property_not_found&)'
>>>>>> ../../../boost/graph/parallel/properties.hpp:95: note: candidates are:
>>>>>> T
>>>>>>
>>>>>>
>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T)
>>>>>> const [with T = boost::detail::error_property_not_found]
>>>>>> ../../../boost/graph/parallel/properties.hpp:96: note:
>>>>>> T
>>>>>>
>>>>>>
>>>>>> boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T,
>>>>>> T, T) const [with T = boost::detail::error_property_not_found]
>>>>>>
>>>>>>
>>>>>> Jeremiah, Do you think that I should file a bug report for this.
>>>>>>
>>>>>>  Although I was hoping (and actually needed quite urgently) that it
>>>>> would
>>>>> be
>>>>> minor issue and get fixed quickly.
>>>>>
>>>>>
>>>> You need to pass a predecessor map to the algorithm as one of the
>>>> parameters
>>>> (or put it as a part of your graph but making an external property map
>>>> to
>>>> give
>>>> to the algorithm is easier).
>>>>
>>>> Hi Jeremy,
>>>>
>>>
>>>   It took me a while but I finally figure out how to pass the predecessor
>>>> map. Unfortunately it doesn't have any effect. Also, I might be wrong
>>>>  but I
>>>> don't see any logical reason why predecessor map should have any bearing
>>>> on
>>>> the correctness of the depth. I have attached the new code.  I am not
>>>> able
>>>> to print out the predecessor because I am not able to figure out its
>>>> type.
>>>> Maybe you could help me resolve this.
>>>>
>>>>
>>> It would be nice to have this code running. I need to profile graph
>>> performance on a new machine by tomorrow. Again, thanks for you patience
>>> and
>>> time. I really appreciate you looking into this.
>>>
>>> Hi Jeremiah,
>>>
>>>   Was just wondering if you had time to look into this or any suggestion
>> on
>> how further proceed. I can get you the output of predecessor map if that
>> would help.
>> Just that I haven't be been able to figure out what the is type of the
>> property map returned by make_distributed_property_map.
>> Please let me know your thoughts.
>>
>
> The person who really knows this library is not around as far as I know; he
> might be on vacation.  The type returned from make_distributed_property_map
> is documented on <URL:
> http://www.osl.iu.edu/research/pbgl/documentation/graph/
> distributed_property_map.html>.  One thing that you could do to debug
> things is to put in your own color map and look at what values it ends up
> with at the end of the algorithm, and possibly even to put in a local color
> map that prints out when elements are changed.  That might be a lot of work
> for what could end up being an obvious problem (that I just don't know how
> to diagnose), though.  BTW, does the example in
> libs/graph_parallel/example/breadth_first_search.cpp work for you?  It
> appears to be doing the same thing you want to do.  If that works, it could
> be a problem in your visitor.
>
>
> I derived this code from graph_parallel/example/breadth_first_search.cpp.
The problem is that I don't understand the input and the output of the
example code. It would be great if I could get an explanation for  the
format of the input file. Then I can transform my graph into that  format
and pass to the algorithm. That would be enough for my current purpose.

As time permits I would try out your suggestions and let know of update. In
the meantime I am hoping that I would get input from other relevant authors.

Thanks,
Sandeep