Re: [boost] [Graph] iterator range splitting

Subject: Re: [boost] [Graph] iterator range splitting
From: David Abrahams (dave_at_[hidden])
Date: 2008-12-15 12:44:39

on Mon Dec 15 2008, "Tim Keitt" <tkeitt-AT-gmail.com> wrote:

>> What I am trying to achieve is to not have the entire graph in memory.
>> Currently I use shared_container_iterator to iterate over out edges so
>> they are deallocated when there are no more references. I can easily
>> change that by holding onto a reference, but then I might as well copy
>> everything into an adjacency_list since pretty much any use of the
>> IncidenceGraph concept will call out_edges on every vertex.
>>
>> Storing an offset into the array is possible, but awkward as every
>> call to out_edges issues a SQL query and allocates memory, so I would
>> incur that overhead simply to retrieve the out degree (which would
>> then be used to compare to the current value of the offset).

Well, you could also keep a cache of N recently-accessed out_edges
results that would save you from the expense for trivial cases like the
ones you've described.

> Thinking about this more, it seems that if you are going to return
> iterator pairs, then it makes sense to assume they are unique per call
> and you should not compare iterators from different ranges (ie
> subsequent calls). Otherwise, I would suggest that calls like
> out_edges be split into out_edges_begin and out_edges_end because you
> may want very different things to happen when retrieving the beginning
> of a range and the end of a range.

You're making a good point.  

> I will probably revert my code to simply copying the entire graph into
> an adjacency_list. Its a time-space trade-off and for many of the
> algorithms run-time will trump space efficiency anyway. I liked the
> idea of graph classes that use a database for storage, but it seems
> impractical with the current Graph library.

I think you're giving up a little too easily on your ability to do it
within the current library definition, and on influencing the library's
design itself.

As for a decision about changing BGL, I'm not that library's maintainer,
so it's really not up to me.  I tend to look for arguments on both
sides, which I now have, before I make judgements about things like
this.  I guess the concepts need to be clarified, and clarifying them as
you suggest (less strict) cannot break any code.  If we discover the
need for a StableOutEdgesGraph concept one day, it can certainly be
added.

I'm guessing that if you submit a patch for the library that updates the
code and docs,  and passes the library's test suite (you should test
that yourself), it would probably be accepted.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com