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