Boost图形库：识别顶点

Question

我需要将 Boost 图中的顶点映射到无符号整数。根据这个网站上相关的帖子（1，2），正确的方法是创建一个自定义的顶点类。

struct Vertex { uint32_t index; };
typedef boost::adjacency_list<boost::vecS, boost::vecS,
    boost::directedS, Vertex> BoostGraphType;    

typedef BoostGraphType::vertex_descriptor vertex_desc;

// now i can use
BoostGraphType g; 

vertex_desc vd = boost::add_vertex(g);
g[vd].index = magic;

然而，根据文档(迭代器和描述符的稳定性/失效)，顶点描述符可能会变为无效，这意味着我不应该将它们存储到映射顶点中。

由于我有自定义的顶点类+.index，这应该不是问题。

但是：我如何在以后的某个时间检索特定索引的顶点描述符？而且怎样才能做到不进行线性搜索？

或者说，是否有比使用这样的自定义顶点类更好的方法来保持每个顶点的持久ID？

- Wilbert

Answer 1

当你的图是adjacency_list<boost::vecS, boost::vecS, ...时，顶点描述符是整数。当你删除一个顶点时，一些顶点描述符可能会变得无效；同样，当你删除一条边时，一些边描述符也会变得无效。如果你从不删除图元素，则这些整数描述符仍然有效。

正如BGL文档所述，“如果你希望你的顶点和边描述符稳定（永远不会失效），则使用listS或setS作为邻接表的VertexList和OutEdgeList模板参数。”

请注意，如果你使用adjacency_list<boost::listS,...，你可能需要额外努力生成和更新名为vertex_index的属性。许多算法在没有它的情况下无法工作。更多细节请参见https://dev59.com/gXbZa4cB1Zd3GeqPGX7A#19758844。

- Michael Simbirsky