[BGL] adjacency_iterator invalidation with adjacency_list<listS, listS, unorderedS>
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 -- 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.
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_l... Sent from the Boost - Users mailing list archive at Nabble.com.
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.
That behavior should actually be correct since an adjacency iterator is just a wrapper around an out edge iterator. I haven't looked at the documentation on adjacency iterator invalidation, so it the docs may be incorrect. Andrew Sutton andrew.n.sutton@gmail.com
Andrew Sutton-2 wrote:
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.
That behavior should actually be correct since an adjacency iterator is just a wrapper around an out edge iterator. I haven't looked at the documentation on adjacency iterator invalidation, so it the docs may be incorrect.
That makes things a bit clearer. However, in the code I provided, I'm incrementing the adjacency_iterator prior to deleting the out edge to which it corresponds. My assumption was that (when using listS) deletion of an out edge would invalidate an out_edge iterator or an edge descriptor if and only if the iterator or descriptor were pointing to the deleted element at the time of its deletion. It seems, however, that deletion of any out edge invalidates the iterator. Is that truly the case, or have I made a mistake? If it is the case, can anyone explain why that limitation is required? -- 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.
Andrew Sutton-2 wrote:
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?
That behavior should actually be correct since an adjacency iterator is just a wrapper around an out edge iterator. I haven't looked at the documentation on adjacency iterator invalidation, so it the docs may be incorrect.
In keeping with your comments, I have tried with both out edge iterators and adjacency iterators in the below simplified examples. Both indeed exhibit the same behavior, but they seem to invalidate the iterators, when (according to the documentation) the iterators should remain valid. There must be a good technical reason why these iterators are invalidated. If anyone can explain that to me, I would greatly appreciate it. In any event, if someone else can confirm this, I think the documentation should be changed. Two simple functions that should work but don't (see previous post for typedefs): void DeleteNeighborEdges_AdjIter(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; Vertex vi = *avi; clear_vertex(vi,g); //******ERROR: avinext appears invalid*******// } } void DeleteNeighborEdges_OutEdgeIter(Vertex v, Graph& g) { typedef boost::graph_traits<Graph>::out_edge_iterator OutEdgeIt; OutEdgeIt oei, oeinext, oe_end; tie(oei, oe_end)=out_edges(v,g); for (oeinext=oei; oei != oe_end; oei=oeinext) { ++oeinext; Vertex vi = target(*oei,g); clear_vertex(vi,g); //******ERROR: oeinext appears invalid*******// } } -- 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.
In keeping with your comments, I have tried with both out edge iterators and adjacency iterators in the below simplified examples. Both indeed exhibit the same behavior, but they seem to invalidate the iterators, when (according to the documentation) the iterators should remain valid. There must be a good technical reason why these iterators are invalidated. If anyone can explain that to me, I would greatly appreciate it. In any event, if someone else can confirm this, I think the documentation should be changed.
I think the problem comes from the graph being undirected, which can cause some interesting problems. The graph actually doubles up on out edges so that a single undirected edge is actually two distinct edges that are stored in the out edge list of each vertex-- one (u, v) the other (v, u). Each of these out edges refers to the same edge stored on the graph (via a ptr or something like that). Basically, its giving the impression that its undirected, but it's not really. When you clear a vertex, you're removing all of the corresponding edges from each adjacent vertex and the "globally" stored edge. What happens, when you see the failures, is that you're actually removing a reciprical edge out from underneath the avinext or oeinext iterator, invalidating it. Basically, you can probably assume that clear_vertex will invalidate any iterators referring to the vertex being cleared for an undirected graph. Andrew Sutton andrew.n.sutton@gmail.com
participants (2)
-
Andrew Sutton -
cobalto