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