Re: [boost] [Graph] iterator range splitting

Subject: Re: [boost] [Graph] iterator range splitting
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2008-12-16 09:22:51

>
> > 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_at_[hidden]