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 don't know that I agree with this - or perhaps I conditionally agree, depending on the concepts modeled by the custom graph - who knows. The IncidenceGraph, which defines the out_edges requirement is intended to abstract a view over a container. For adjacency lists, this is a transform iterator over a container's range. For an incidence list or adjaceny matrix, it's probably filter+transform iterator over the list of edges or row/column of a vertex. If you assume this property holds: make_pair(C.begin(), c.end()) == make_pair(C.begin(), C.end()) then it *should* follow that the ranges of adapted iterators also exhibit the same property. This is probably expressable as some kind of congruence relation. Something like: typedef adapted_iterator<C::iterator> iterator; make_pair(iterator(C.begin()), iterator(C.end())) == make_pair(iterator(C.begin()), iterator(C.end())) Obviously, allocating the range from an SQL query is substantially different than pulling iterators from an in-memory container, but I think I would argue that this property should be preserved. If you can make your out_edge_iterators model this behavior, then your graph should be interoperable. Of course, this is all conjeture, undocumented and up for discussion.
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.
Agreed. I don't think that SQL-based graphs are necessarily impractical with the current implementation - just difficult to adapt. Of course, the same can probably be said about *any* custom graph type.
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.
I'm not against adding *begin and *end variants for the iterator ranges, but I'm not sure how much it actually gives you - except avoiding this notation: *vertices(g).first. Andrew Sutton andrew.n.sutton@gmail.com