我有一个带有VertexList = vecS的Boost图 .
typedef adjacency_list <listS, vecS, undirectedS, TrackInformation, LinkInformation> TracksConnectionGraph;
现在我想迭代我的顶点并删除那些具有特定属性的顶点 . 我怎样才能做到这一点？
问题是每当我调用remove_vertex时，图中顶点的迭代器以及顶点描述符都会失效 .
我认为（在合理的时间内）使用 vecS 作为模板参数是不可能的 . 看看Boost的文档说：
vecS
如果adjacency_list的VertexList模板参数是vecS，则此操作将使图形的所有顶点描述符，边描述符和迭代器无效 . <...>如果需要经常使用remove_vertex（）函数，则listS选择器是VertexList模板参数的更好选择 .
在 listS 的情况下，迭代器不会通过调用 remove_vertex 无效，除非迭代器指向已移除的实际顶点 .
listS
remove_vertex
可能是，在迭代之前你可以制作特殊的“Trash”顶点，在迭代过程中你将所有删除节点连接到该Trash-vertex，并在迭代后删除所有“Trash-connected”顶点？
您的边存储在std :: vector中 . 如果您有N个顶点，则所有顶点都从0到N编号 . 如果删除一个顶点，则顶点将从o重新编号为N-1 . 因此，您的描述符将无效 .
但是，可能存在一个工作： - 从N向下迭代到0 - 测试您的节点并在必要时删除它
这假设（我不确定，但相当自信）它只会重新编号你刚刚删除的顶点 after .
如果你经常进行这种操作，它可能会相当慢，具体取决于你的图形大小 .
如果这种方法不起作用，你将不得不从旧方法构建一个新图形（通过预先计算你将拥有多少个顶点和边缘，这实际上可能非常快） .
所以，对不起，没有真正的答案，但我希望你能设法从中得到一些东西 .
3 回答
我认为（在合理的时间内）使用
vecS作为模板参数是不可能的 . 看看Boost的文档说：在
listS的情况下，迭代器不会通过调用remove_vertex无效，除非迭代器指向已移除的实际顶点 .可能是，在迭代之前你可以制作特殊的“Trash”顶点，在迭代过程中你将所有删除节点连接到该Trash-vertex，并在迭代后删除所有“Trash-connected”顶点？
您的边存储在std :: vector中 . 如果您有N个顶点，则所有顶点都从0到N编号 . 如果删除一个顶点，则顶点将从o重新编号为N-1 . 因此，您的描述符将无效 .
但是，可能存在一个工作： - 从N向下迭代到0 - 测试您的节点并在必要时删除它
这假设（我不确定，但相当自信）它只会重新编号你刚刚删除的顶点 after .
如果你经常进行这种操作，它可能会相当慢，具体取决于你的图形大小 .
如果这种方法不起作用，你将不得不从旧方法构建一个新图形（通过预先计算你将拥有多少个顶点和边缘，这实际上可能非常快） .
所以，对不起，没有真正的答案，但我希望你能设法从中得到一些东西 .