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-30 09:41:15

On Thu, 29 Oct 2009, Sandeep Gupta wrote:

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

This is what I could tell from the code.

Input: 
http://people.sc.fsu.edu/~burkardt/data/metis_graph/metis_graph.html

Output:
http://www.graphviz.org/doc/info/lang.html

-- Jeremiah Willcock