c++ - 从 boost::adjacency_list 图中删除多个顶点

Question

我正在使用 boost graph_traits 并定义了这样一个图:

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

我的每个顶点都附有坐标，我打算找到重复的顶点(同一位置的顶点)。所以我构建了一个包含这些“集群”的列表:

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

现在我尝试将每个簇合并到一个顶点(顶点列表)中。为此，我调用集群的每个顶点 clusters[i]:

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

但是我注意到仍然存在重复项。我猜想这与删除时索引的变化有关，因为我使用 vecS 作为顶点列表。

这是什么原因，我该如何解决？

Answer 1

对于 vectorS，描述符与迭代器一样不稳定:它们在插入/删除时失效。参见 Iterator and Descriptor Stability/Invalidation

当然，那里描述的解决方案(使用 listS)可能不适用于您的情况。

在这种情况下，请重新考虑您的问题，并考虑过滤图形(实际上不删除顶点)或将顶点标记为已删除。请参阅此处获取灵感:

• Remove 100,000+ nodes from a Boost graph (也是_jv的评论)