[graph][iterators] csr graph and reverse iterator problem
Hi, All I'm using Boost.Graph and Boost.Iterators. When I use the compressed_sparse_row_graph with reverse_iterator, I ran into a problem. When I dereference the reverse_iterator of compressed_sparse_row_graph's iterator, invalid memory access occurs. On g++ version 4.6.0 with -Os option, The output is below. 0 1 1 0 0 1 134526756 3218710936 1 0 And I also checked where the invalid memory access occurred using valgrind. ==2341== Invalid read of size 4 ==2341== at 0x8048DE7: test_csr_graph() (rev_iter.cpp:45) ==2341== by 0x8048FB3: main (rev_iter.cpp:59) ==2341== Address 0xbe825f88 is just below the stack ptr. To suppress, use: --workaround-gcc296-bugs=yes ==2341== 1 ==2341== Invalid read of size 4 ==2341== at 0x8048E31: test_csr_graph() (rev_iter.cpp:46) ==2341== by 0x8048FB3: main (rev_iter.cpp:59) ==2341== Address 0xbe825f88 is just below the stack ptr. To suppress, use: --workaround-gcc296-bugs=yes ==2341== This result indicates the code below is suspicious. std::cout << *rib++ << std::endl; // NG Why? Line 45 std::cout << *rib++ << std::endl; // NG Why? Line 46 But... boost::tie(ib, ie) = boost::vertices(g); std::cout << *--ie << std::endl; // OK std::cout << *--ie << std::endl; // OK It is OK. Here is the source code that reproduces the problem. ------------ begin ------------- #include <boost/iterator/reverse_iterator.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/compressed_sparse_row_graph.hpp> #include <iostream> #include <cassert> void test_graph() { typedef boost::adjacency_list<> graph_type; graph_type g(2); boost::graph_traits<graph_type>::vertex_iterator ib, ie; { boost::tie(ib, ie) = boost::vertices(g); std::cout << *ib++ << std::endl; // OK std::cout << *ib++ << std::endl; // OK assert(ib == ie); } { boost::tie(ib, ie) = boost::vertices(g); boost::reverse_iterator<boost::graph_traits<graph_type>::vertex_iterator> rib(ie); boost::reverse_iterator<boost::graph_traits<graph_type>::vertex_iterator> rie(ib); std::cout << *rib++ << std::endl; // OK std::cout << *rib++ << std::endl; // OK assert(rib == rie); } } void test_csr_graph() { typedef boost::compressed_sparse_row_graph<> graph_type; std::pair<int, int> e(0, 1); std::pair<int, int> es[] = { e }; graph_type g(boost::edges_are_unsorted, &es[0], &es[1], 2); boost::graph_traits<graph_type>::vertex_iterator ib, ie; { boost::tie(ib, ie) = boost::vertices(g); std::cout << *ib++ << std::endl; // OK std::cout << *ib++ << std::endl; // OK assert(ib == ie); } { boost::tie(ib, ie) = boost::vertices(g); boost::reverse_iterator<boost::graph_traits<graph_type>::vertex_iterator> rib(ie); boost::reverse_iterator<boost::graph_traits<graph_type>::vertex_iterator> rie(ib); std::cout << *rib++ << std::endl; // NG Why? Line 45 std::cout << *rib++ << std::endl; // NG Why? Line 46 assert(rib == rie); } { boost::tie(ib, ie) = boost::vertices(g); std::cout << *--ie << std::endl; // OK std::cout << *--ie << std::endl; // OK assert(ib == ie); } } int main() { test_graph(); test_csr_graph(); } ------------ end ------------- Why does the invalid memory access occur? Am I misusing the libraries? Thanks, Takatoshi
On Wed, 7 Sep 2011, Takatoshi Kondo wrote:
Hi, All
I'm using Boost.Graph and Boost.Iterators.
When I use the compressed_sparse_row_graph with reverse_iterator, I ran into a problem.
When I dereference the reverse_iterator of compressed_sparse_row_graph's iterator, invalid memory access occurs.
I tried my copy of GCC 4.6, and get a similar problem. It does not seem to related to Boost.Graph at all, though; I get the same result (use of uninitialized value) with counting_iterators that are created directly (CSR graph vertex_iterators are counting_iterators). I changed the subject line to emphasize the Boost.Iterator issue. Here is a trimmed-down program that has similar problems, even with optimization disabled: #include <boost/iterator/reverse_iterator.hpp> #include <boost/iterator/counting_iterator.hpp> #include <iostream> int main() { boost::counting_iterator<int> ie(2); boost::reverse_iterator<boost::counting_iterator<int> > rib(ie); std::cout << *rib << std::endl; return 0; } -- Jeremiah Willcock
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) Regards, Michel
Hi, On Thu, 8 Sep 2011 07:48:01 +0900 Michel Morin <mimomorin@gmail.com> 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 :) Regards, Takatoshi
On Thu, 8 Sep 2011, Takatoshi Kondo wrote:
Hi,
On Thu, 8 Sep 2011 07:48:01 +0900 Michel Morin <mimomorin@gmail.com> 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). -- Jeremiah Willcock
On Thu, 8 Sep 2011 14:31:10 -0400 (EDT) Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Thu, 8 Sep 2011, Takatoshi Kondo wrote:
Hi,
On Thu, 8 Sep 2011 07:48:01 +0900 Michel Morin <mimomorin@gmail.com> 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.htm... 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? 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? Thanks, Takatoshi
On Fri, 9 Sep 2011, Takatoshi Kondo wrote:
On Thu, 8 Sep 2011 14:31:10 -0400 (EDT) Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Thu, 8 Sep 2011, Takatoshi Kondo wrote:
Hi,
On Thu, 8 Sep 2011 07:48:01 +0900 Michel Morin <mimomorin@gmail.com> 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.htm...
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.
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? -- Jeremiah Willcock
On Sat, Sep 10, 2011 at 12:29 AM, Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Fri, 9 Sep 2011, Takatoshi Kondo wrote:
On Thu, 8 Sep 2011 14:31:10 -0400 (EDT) Jeremiah Willcock <jewillco@osl.iu.edu> wrote:
On Thu, 8 Sep 2011, Takatoshi Kondo wrote:
Hi,
On Thu, 8 Sep 2011 07:48:01 +0900 Michel Morin <mimomorin@gmail.com> 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.htm...
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
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
On Sep 9, 2011, at 5:02 AM, Takatoshi Kondo <kondo@t.email.ne.jp> wrote:
One further note -- there is nothing in the BGL requirements that states that vertex_iterators need to be bidirectional
Out of curiosity, is it ever not the case for any of BGL's graph classes? Or is the requirement loose for the sake of external graph libs? Cheers, Gordon (thinking an slist of vertices must be rare)
On Sat, 10 Sep 2011, Gordon Woodhull wrote:
On Sep 9, 2011, at 5:02 AM, Takatoshi Kondo <kondo@t.email.ne.jp> wrote:
One further note -- there is nothing in the BGL requirements that states that vertex_iterators need to be bidirectional
Out of curiosity, is it ever not the case for any of BGL's graph classes? Or is the requirement loose for the sake of external graph libs?
The adjacency_list class does support an slist of vertices as far as I know. The documentation is incorrect on this, though (it says the vertex iterator is always at least bidirectional). I would imagine that filtered_iterator (used by filtered_graph) produces bidirectional iterators as well, but I'm not sure about that. -- Jeremiah Willcock
participants (5)
-
Gordon Woodhull -
Jeremiah Willcock -
Michel Morin -
Takatoshi Kondo -
Takatoshi Kondo