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.