我需要将 Boost Graph 中的顶点映射到一个无符号整数。我从本网站(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;
但是，根据文档 (Iterator and Descriptor Stability/Invalidation)，顶点描述符可能会变得无效，这意味着我不应该存储它们来映射顶点。
因为我有我的自定义顶点类 + .index，所以这应该不是问题。
但是:以后如何检索特定索引的 vertex_descriptor？如果没有线性搜索，我该怎么做？
或者有没有比自定义顶点类更好的方法来为每个顶点保留一个持久性 ID？
最佳答案
当你的图表是 adjacency_list<boost::vecS, boost::vecS, ...那么顶点描述符是整数。删除顶点时，某些顶点描述符可能会变得无效；类似地，当您删除一条边时，一些边描述符会变得无效。如果您从不删除图形元素，那么这些整数描述符仍然有效。
正如 BGL 文档所述，“如果您希望顶点和边描述符稳定(永不失效)，则对 adjacency_list 的 VertexList 和 OutEdgeList 模板参数使用 listS 或 setS。”。
请注意，如果您使用 adjacency_list<boost::listS,...您可能需要付出额外的努力来生成和更新名为 vertex_index 的属性。没有它，许多算法将无法工作。在此处查看更多详细信息 https://stackoverflow.com/a/19758844/2876861
关于performance - Boost Graph 识别顶点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16736093/