Re: [Boost-users] [BGL] adjacency_iterator invalidation with adjacency_list<listS, listS, unorderedS>

Subject: Re: [Boost-users] [BGL] adjacency_iterator invalidation with adjacency_list<listS, listS, unorderedS>
From: cobalto (scott.a.merritt_at_[hidden])
Date: 2010-02-23 13:21:01

cobalto wrote:
> 
> According to
> http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/adjacency_list.html, 
> adjacency_iterators into adjacency_list<listS, listS, unorderedS, ... >
> graphs should not be invalidated by 
> calls to clear_vertex() and remove_vertex().
> 
> However, running the below code results in iterator invalidation directly
> following the call to clear_vertex()
> From most likely to least likely, am I 1) doing something wrong,
> 2)misreading something in the documentation, or 3) encountering a bug?
> 
> using namespace boost; 
> typedef property<vertex_name_t, unsigned short> usVertName;
> typedef boost::adjacency_list< listS, listS, undirectedS, usVertName >
> Graph;
> typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
> 
> void RemoveVertAndNeighbors(Vertex v, Graph& g)
> {
>    typedef boost::graph_traits<Graph>::adjacency_iterator AdjVertIt;
>    AdjVertIt avi, avinext, av_end;
>    tie(avi, av_end)=adjacent_vertices(v,g);
>    for (avinext=avi; avi != av_end; avi=avinext)
>    {
>       ++avinext;
>       //avinext is a valid iterator here
>       clear_vertex(*avi,g); //Should Invalidate Edge Iterators and Edge
> Refs that touch Vertex *avi 
>       //******ERROR: avinext appears invalid*******//
>       //either no longer points to the same element or otherwise crashes
> the program
>       remove_vertex(*avi,g); //Should Invalidate avi and any other Vertex
> Reference pointing to *avi
>                                       //But should not affect avinext 
>    }
>    remove_vertex(v,g);
> }
> 
> Any Help is greatly Appreciated
> 

More Info:
a 2-pass method where I make a std::list of vertex descriptors and then
process these vertices works.
This means vertex descriptors are not being invalidated, but
adjacency_iterators are.

Substituting the following code in the above example avoids the run-time
error :

void RemoveVertAndNeighbors( Vertex v, Graph &g)
{
        typedef boost::graph_traits<Graph>::adjacency_iterator AdjVertIt;
        std::list<Vertex> vl;
        AdjVertIt avi, av_end;
        for (tie(avi, av_end) = adjacent_vertices(v, g); avi != av_end; ++avi)
                vl.push_back(*avi);
        for (std::list<Vertex>::iterator it = vl.begin(); it != vl.end(); ++it
        {
                clear_vertex((*it), g); 
                remove_vertex((*it), g);
        }
        remove_vertex(v,g);
        return true;
}

I'm wondering if the documentation is incorrect. Perhaps it is just
imprecise, and removing any edge from the source vertex of an
adjacency_iterator invalidates that iterator? 

Anyone with additional insight would be very helpful. 

-- 
View this message in context: http://old.nabble.com/-BGL--adjacency_iterator-invalidation-with-adjacency_list%3ClistS%2C-listS%2C-unorderedS%3E-tp27647214p27707861.html
Sent from the Boost - Users mailing list archive at Nabble.com.