[boost] [graph][iterators] csr graph and reverse iterator problem

Subject: [boost] [graph][iterators] csr graph and reverse iterator problem
From: Takatoshi Kondo (kondo_at_[hidden])
Date: 2011-09-07 07:48:47

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