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

23 Feb 2010

      cobalto wrote:
...
According to
http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/adjacency_list.html, 
adjacency_iterators into adjacency_list
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 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_l...
Sent from the Boost - Users mailing list archive at Nabble.com.