当图VertexList=vecS时remove_vertex
我有一个带有 VertexList=vecS 的 Boost Graph。
typedef adjacency_list <listS, vecS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;
现在我想迭代我的顶点并删除那些具有特定属性的顶点。我该怎么做？
问题是每当我调用remove_vertex时，图中顶点的迭代器以及顶点描述符都会失效。
I have a Boost Graph with VertexList=vecS.
typedef adjacency_list <listS, vecS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;
Now I want to iterate through my vertices and remove those that have a specific property. How can I do this?
The problem is whenever I call remove_vertex, the iterator to the vertices in the graph along with the vertex descriptors are invalidated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
也许，在迭代之前，您可以创建特殊的“垃圾”顶点，在迭代期间，您将所有要删除的节点连接到该垃圾顶点，并在迭代之后删除所有“垃圾连接”顶点？
May be, before iteration you can make special "Trash" vertex, during iteration you connect all nodes-for-deletion to that Trash-vertex and, after iteration, delete all "Trash-connected" vertices?
您的边缘存储在 std::vector 中。如果有 N 个顶点，则所有顶点的编号从 0 到 N。如果删除一个，则顶点将从 o 重新编号到 N-1。因此，您的描述符将无效。
但是，可能有一个解决方法：
– 从 N 迭代到 0
– 测试您的节点并在必要时删除它
这假设（我不确定，但相当有信心）它只会对您刚刚删除的顶点之后重新编号。
如果您经常进行此操作，则根据图表的大小，它可能会相当慢。
如果这种方法不起作用，您将不得不从旧图构建一个新图（通过预先计算您将拥有多少个顶点和边，这实际上可能相当快）。
所以，抱歉，没有真正的答案，但我希望你能从中得到一些东西。
Your edges are stored in an std::vector. If you have N vertices, then all vertices are numbered from 0 to N. If you delete one, then your vertices will be renumbered from o to N-1. Therefor, your descriptor will be invalidated.
However, there might be a work arround :
– iterate from N down to 0
– test your node and delete it if necessary
This supposes (and I'm not sure, but rather confident) that it will only renumber the vertices after the one you've just deleted.
If you do this manipulation a lot, it might be rather slow depending on your graph's size.
If that approach doesn't work, you'll have to build a new graph from the old one (by pre-computing how many vertices and edges you will have, this might actually be reasonnably fast).
So, sorry, no real answer, but I hope you'll manage to get something out of it.
我认为（在合理的时间内）使用 vecS 作为模板参数是不可能的。看看 Boost 文档是怎么说的：
对于
listS，迭代器不会通过调用remove_vertex而失效，除非迭代器指向被删除的实际顶点。I don't think it is possible (in a reasonable time) with
vecSas a template parameter. Look what Boost documentation says:In case of
listSthe iterators are not invalidated by callingremove_vertexunless the iterator is pointing to the actual vertex that was removed.