Re: [boost] [Graph] iterator range splitting

Subject: Re: [boost] [Graph] iterator range splitting
From: Sandeep Gupta (gupta.sandeep_at_[hidden])
Date: 2009-06-27 20:23:01

On Sat, Jun 27, 2009 at 3:44 PM, Tim Keitt<tkeitt_at_[hidden]> wrote:
> On Fri, Jun 26, 2009 at 6:33 PM, Sandeep Gupta <gupta.sandeep_at_[hidden]>wrote:
>
>> On Fri, Jun 26, 2009 at 4:15 PM, Jeremiah Willcock<jewillco_at_[hidden]>
>> wrote:
>> > On Fri, 26 Jun 2009, Sandeep Gupta wrote:
>> >
>> >> Hi Jeremiah,
>> >> The issue Tim brought up was regarding the case when the graph is not
>> >> fully read in the main memory. Instead memory is allocated per
>> >> out_edges invocation. For this to work the algorithm should not break
>> >> range obtained from a out_edges call. However current implementation
>> >> of dijkstra's does exactly that.
>> >>
>> >> --  an example of range split: "depth_first_search(g, vis, color,
>> >> *vertices(g).first);"
>> >>
>> >> Tim proposed that he should be able to provide patch to fix such
>> >> cases. I hope he has because for my current project I intend to
>> >> process a graph stored externally.
>> >
>> > What is wrong with the call to depth_first_search?  That is getting a
>> single
>> > vertex, not the whole range.  I applied the kinds of things that were in
>> his
>> > patch (not always in the same way), so his issues should be fixed.  BGL
>> was
>> > not built for out-of-core applications, though, so a lot of the changes
>> are
>> > implementation details that can't really be relied upon.  Are you trying
>> to
>> > page in and out edge sets as needed, and that's why you need ranges to be
>> > used more consistently?
>> >
>>
>> Yes, ideally i would like to page-in and -out the edge sets.  Glad to
>> know that these issues are fixed. I believe  that as long as the calls
>> to out_edges are indepenet/decoupled  paging-in and -out should work.
>> Although I will double check things once i get around to implementing
>
>
> Sandeep,
>
> Check the current trunk. I think all the "problem" cases are now fixed. Most
> notably, the iteration macros now only compare iterators from the same call
> to vertices, edges, et al. so algorithms that rely on those will work in
> cases where each call produces a new iterator range. The changes were
> motivated by storing edges in postgresql: https://launchpad.net/postgraph.
>
> THK
>

Would do so. Thanks for clarifying and also for postgraph.

-sandeep