CODEWITHSUNDEEP
c++boostgraph
Chris
Chris

Reputation: 1306

Removing multiple vertices from a boost::adjacency_list graph

I'm using boost graph_traits and defined a graph like this:

typedef boost::adjacency_list <boost::setS, boost::vecS, boost::undirectedS, NodeInfo, EdgeInfo> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

Each of my vertices has coordinates attatched and I intend to find duplicate vertices (vertices in the same location). So I build a list that contains these "clusters":

std::vector<std::vector<Vertex>> clusters;

Now I tried to merge each cluster in one single vertex (list of vertices). To do this I call for each vertex of a cluster clusters[i]:

boost::clear_vertex(v, graph)
boost::remove_vertex(v, graph);

However I noticed that still duplicates remain. I guess that it's related to a changes in indices while deleting as I use vecS for the vertex-list.

What is the reason for this and how can I solve it?

Upvotes: 3

Views: 824

Answers (1)

sehe
sehe

Reputation: 392911

For vectorS the descriptors are just as unstable as iterators: they get invalidated on insert/remove. See Iterator and Descriptor Stability/Invalidation

Of course the solution described there (using listS) might not apply to your situation.

In that case, rethink your problem, and consider filtering the graph (without actually removing vertices) or mark vertices as deleted. See here for inspiration:

Upvotes: 2

Related Questions