Re: [boost] [Graph] iterator range splitting

Subject: Re: [boost] [Graph] iterator range splitting
From: Tim Keitt (tkeitt_at_[hidden])
Date: 2009-06-27 18:44:32

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

>
> it.
>
> -thanks
> sandeep
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>

-- 
Timothy H. Keitt
http://www.keittlab.org/