c++ - 当图 VertexList=vecS 时 remove_vertex

Question

我有一个带有 VertexList=vecS 的 Boost Graph。

typedef adjacency_list <listS, vecS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;

现在我想遍历我的顶点并删除那些具有特定属性的顶点。我怎样才能做到这一点？

问题是每当我调用 remove_vertex 时，图中顶点的迭代器以及顶点描述符都会失效。

Answer 1

可能是，在迭代之前，您可以制作特殊的“垃圾”顶点，在迭代期间，您将所有删除节点连接到该垃圾顶点，并在迭代之后，删除所有“垃圾连接”顶点？

Answer 2

您的边缘存储在 std::vector 中。如果您有 N 个顶点，那么所有顶点的编号从 0 到 N。如果您删除一个，那么您的顶点将从 o 重新编号到 N-1。因此，您的描述符将失效。

但是，可能有一个解决方法： – 从 N 迭代到 0 – 测试您的节点并在必要时将其删除

这假设（我不确定，但相当有信心）它只会在您刚刚删除的顶点之后重新编号顶点。

如果您经常执行此操作，则可能会相当慢，具体取决于您的图表大小。

如果这种方法不起作用，您将不得不从旧图构建一个新图（通过预先计算您将拥有多少顶点和边，这实际上可能相当快）。

所以，对不起，没有真正的答案，但我希望你能从中得到一些东西。

Answer 3

我认为（在合理的时间内）vecS作为模板参数是不可能的。看看 Boost 文档是怎么说的：

如果was的VertexList模板参数，则该操作使图的所有顶点描述符、边描述符和迭代器无效。<...> 如果您需要频繁使用该函数，则选择器是模板参数的更好选择。adjacency_listvecSremove_vertex()listSVertexList

如果listS迭代器不会通过调用无效，remove_vertex除非迭代器指向被删除的实际顶点。