Re: [boost] [Graph] iterator range splitting

Subject: Re: [boost] [Graph] iterator range splitting
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-06-26 19:15:24

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?

-- Jeremiah Willcock