Boost logo

Boost :

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

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at