Re: [boost] [iterator] counting_iterator and reverse iterator problem (was: [graph][iterators] csr graph and reverse iterator problem)

Subject: Re: [boost] [iterator] counting_iterator and reverse iterator problem (was: [graph][iterators] csr graph and reverse iterator problem)
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2011-09-11 17:46:35

On Sep 11, 2011, at 7:42 AM, Takatoshi Kondo wrote:

>>> If the custom container doesn't satisfy the concept, compile error would
>>> occur.
>>> I believe when I choose the container that has random access iterator for
>>> VertexList,
>>> I can rely on the function vertices(g) returns a pair of random access
>>> iterator.
>>> Am I wrong?
>> 
>> Yes, you are right, but whether the iterator is random access is an
>> implementation detail.
> 
> I agree.
> There is no documents that  boost::graph_traits<G>::vertex_iterator is
> same as container iterator provided by template parameter.

IMO it's not completely an implementation detail if the user has requested it.  It's more like, if you want to write code that's at all generic, you must abide by the concepts.  If you use something that's outside of those, it won't necessarily work with a different graph implementation.

A more complex example: suppose you wanted named vertices/edges.  You could define a container_gen to use string->V/E maps, but the BGL concepts won't adapt e.g. to let you do 
out_edge(v,g,"e") 
or 
out_edges(v,g)["e"]

I'm not saying that they should - keeping track of the parameterized concepts would be really confusing, and algorithms would get less compatible.  I just think it's a curious tension between BGL as the concepts, and as a graph container generator.

Cheers,
Gordon