On Thu, 31 May 2012, Sergey Mitsyn wrote:
Hi all,
I know that while using vecS for vertices one has no vertex iterator stability upon removing vertices. But I have a question if there exists something like vertex _index_ stability. The documentation says that indices for vertices are automatically adjusted so that they are still in contiguous range, but it is not specified how it is done. Is it okay to assume that if a vertex with an index I is removed, then vertices with indices < I have their indices unchanged, while vertices with indices > I have their indices decreased by one?
Yes, that is how it works internally, but that is not documented behavior; it probably should be, however. It also does not apply to vertex iterators; those can change to completely unrelated values on any vertex insertion/deletion.
The actual problem is removing all vertices meeting some condition. Is the following code ok?
// traverse all vertices and remove those for which predicate // condition_to_remove_vertex returns true.
// graph is adjacency_list<.., vecS, ...>
vertex_iterator vi = vertices(graph).first, vi_end = vertices(graph).second;
while (vi != vi_end) { if (condition_to_remove_vertex(vi, graph)) { vertices_size_type end_index = vertex_index[*vi_end] , vi_index = vertex_index[*vi];
remove_vertex_f(*vi, graph); // vi and vi_end are invalid
--end_index;
vi = vertices(graph).first + vi_index; vi_end = vertices(graph).first + end_index; // now vi and vi_end are valid again } else ++vi; }
This way seems to be more effective than to start iteration again every time a vertex is removed.
Yes, that should work. Rather than using vertices(graph).first + vi_index, use vertex(vi_index, graph); I believe the order is guaranteed to be the same between those, and it is in practice. You might also want to have the loop be over the vertex numbers: for (vertices_size_type i = 0; i < num_vertices(graph); /*Incremented in loop*/) { vertex_descriptor v = vertex(i, graph); if (condition(v, graph) { remove_vertex(v, graph); } else { ++i; } } Depending on what you are doing, you might also want to consider using filtered_graph with a bitmap representing which vertices are deleted. That will keep everything valid (even for vecS), including external property maps based on the vertex index numbers. -- Jeremiah Willcock