从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作为顶点列表，导致索引发生了变化。

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

- Chris

Answer 1

对于vectorS，描述符就像迭代器一样不稳定：在插入/删除时它们会失效。请参见迭代器和描述符的稳定性/失效性。

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

在这种情况下，请重新考虑您的问题，并考虑过滤图形（而不实际删除顶点）或将顶点标记为已删除。在此处查看灵感：

• 从Boost图中删除100,000个以上节点（还有_jv的评论）

- sehe

---

是否可以对要删除的顶点列表按降序进行排序，并以这种方式安全地删除它们（因为仅删除索引i应影响std :: vector中的索引> i）？ - Chris

原则上是可以的。但是我会坚持使用文档化的稳定性/失效保证。而且，“remove_vertex()”在使用VertexList=vecS的邻接表时，会使图形的所有迭代器和描述符失效，这并不给你任何余地。 - sehe

我测试了一下，结果并不如我所预期的那样。也许我的内部工作方式的假设是错误的。现在我尝试使用filtered_graph，但在将其转换回adjacency_list时遇到了问题。 - Chris

http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/copy_graph.html应该是一个很好的帮助。 - sehe