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: Takatoshi Kondo (redboltz_at_[hidden])
Date: 2011-09-11 07:42:37

On Sat, Sep 10, 2011 at 12:29 AM, Jeremiah Willcock <jewillco_at_[hidden]> wrote:
> On Fri, 9 Sep 2011, Takatoshi Kondo wrote:
>
>>
>> On Thu, 8 Sep 2011 14:31:10 -0400 (EDT)
>> Jeremiah Willcock <jewillco_at_[hidden]> wrote:
>>
>>> On Thu, 8 Sep 2011, Takatoshi Kondo wrote:
>>>
>>>> Hi,
>>>>
>>>> On Thu, 8 Sep 2011 07:48:01 +0900
>>>> Michel Morin <mimomorin_at_[hidden]> wrote:
>>>>
>>>>> Relevant ticket (#2640):
>>>>>  https://svn.boost.org/trac/boost/ticket/2640
>>>>>  Legal forward iterators cannot store their referents
>>>>>  (was: counting_iterator::reference lifetime tied to iterator)
>>>>
>>>> Thanks, I've understood what is the problem.
>>>> I think that when we write a generic algrithm using reverse_iterator
>>>> or make own iterator using counting_iterator, we should refer to this
>>>> problem in comment.
>>>>
>>>> Anyway my problem has solved. Thanks again :)
>>>
>>> One further note -- there is nothing in the BGL requirements that states
>>> that vertex_iterators need to be bidirectional, so you cannot rely on
>>> that
>>> being true for arbitrary graph types (see
>>>
>>> http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/VertexListGraph.html).
>>
>> Thanks for the advice. I read the document. My understanding is that
>> concept check's purpose is to constrain the custom containers.
>> e.g.
>>
>> http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/using_adjacency_list.html#sec:custom-storage
>>
>> 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.

>> But in the case of compressed_sparse_row_graph, we can't pass
>> the template parameter as a container selector.The iterator's
>> capability depend on implementation. But it's detail of implementation.
>>
>> Hmm...
>> Should we only rely on MultiPassInputIterator capability?
>
> I think that would be better.  Is there some reason you need a
> reverse_iterator on top?

I'd like to do something to vertices toward front to back, and then
restore(not simple restore) something toward back to front. Of course
I can do that using decrement operation to the iterator instead of
reverse_iterator. But it also requires bidirectional iterator
capability at least. To remove the dependency on bidirectional
iterator, we can use somehow stacking structure on the client side.
But if the vertices iterator has bidirectional iteration capability, I
can do that simpler way.

I think it is desirable to minimize the requirements for custom
container. And BGL has done that.
And I also think it is desirable to maximize the capability of
iterators  that obtain from BGL, as far as it doesn't have
penalty(speed memory etc... ).
I think that providing much capability for BGL's client is better.
I know the current specification. It's a kind of an enhancement request.

Of course the developers who write internal BGL code and generic
algorithm shouldn't depend on such iterators capability.

Anyway my current problem was solved.

Thanks,
Takatoshi