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-29 16:12:38

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.

-- Jeremiah Willcock