3

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?

Chris
  • 1,266
  • 4
  • 16
  • 34

1 Answers1

2

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:

sehe
  • 374,641
  • 47
  • 450
  • 633
  • Is it possible to sort the list of vertices to remove in descending order and remove them this way safely (as the removal of an index i only should affect the indices > i in an std::vector)? – Chris Jan 30 '17 at 12:33
  • In principle, yes. However, I'd stick to the documented stability/invalidation guarantees. And "remove_vertex(), which when used with an adjacency_list where VertexList=vecS, invalidates all iterators and descriptors for the graph" does **not** give you that lee-way. – sehe Jan 30 '17 at 13:20
  • I tested it and it didn't work as I expected. Maybe my assumptions on how it works internally were wrong. Now I tried to use a filtered_graph but have trouble converting it back to an adjacency_list. – Chris Jan 30 '17 at 13:22
  • http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/copy_graph.html should be a good help – sehe Jan 30 '17 at 13:35