c++ - Boost Graph Library : How do I keep a permanant reference to a vertex?(即不受顶点重新编号的影响)

Question

比方说，我想保留对顶点的引用。例如。在有限状态机中，我想标记开始状态和最终状态。首先想到的是Graph:vertex_descriptor。但是，它是一个无符号整数，如果从图中删除了一个顶点，则可以对剩余的顶点重新编号。

那么保留不受顶点移除影响的顶点引用的好方法是什么(当然除非引用的顶点本身被移除)。谢谢!

Answer 1

如果您引用表格“描述符和迭代器失效摘要”。在 this page ，如果您使用 vecS 作为 adjacency_list 的 VertexList 模板参数，您将看到顶点描述符仅在顶点移除期间无效。您希望顶点描述符永远不会失效(除非它们被删除)，您应该改用 listS(或除 vecS 之外的任何其他描述符，尽管对于顶点，你最好只使用 listS)。

我在某些情况下使用过的另一种可能性是，在适用的情况下，将您不想失效的两个(起始、最终)顶点放在图形的最开始(您添加的前两个顶点到图表)。当您这样做时，即使使用 vecS，删除顶点也不会移动第一个顶点的位置(仅移动顶点之后的顶点)。然而，这是一个 hack，你不应该太依赖这个技巧。

我还实现了 adjacency_list 类的替换，它还包括一个池容器选项，它具有 vecS 的大部分优点(例如局部性)但是到处保留顶点描述符。你可以check it out ，但请注意，它还没有完全投入生产。

至于选择引用顶点的方式......答案总是vertex_descriptor。其他任何东西都不是真正安全的。迭代器仅用于遍历，不能用作“指针”。

编辑:如果您需要在通用函数的上下文中测试特定图形类型是否具有“持久”顶点描述符，我不知道是否有任何直接测试，但您可以检查顶点迭代器上的迭代器类别。如果迭代器类别是“随机访问”，那么它通常意味着顶点描述符不是持久的(可能因删除而无效)。通过迭代器类别，我的意思是，来自 std::iterator_traits ，获取 vertex_iterator 的特征。我想这也有点像 hack，但这是一个相当安全的方法。