3

我需要将 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 和 Descriptor Stability/Invalidation），顶点描述符可能会变得无效，这意味着我不应该存储它们来映射顶点。

因为我有我的自定义顶点类 + .index，所以这应该不是问题。

但是：我以后如何检索特定索引的 vertex_descriptor？如果没有线性搜索，我怎么能做到这一点？

或者有没有比这样的自定义顶点类更好的方法来为每个顶点保留一个持久的 id？

4

1 回答 1

3

When your graph is adjacency_list<boost::vecS, boost::vecS, ... then vertex descriptors are integers. Some vertex descriptors can become invalid when you remove a vertex; similarly, some edge descriptors become invalid when you remove an edge. If you never remove graph elements then these integer descriptors remain valid.

As BGL documentation states it, "if you want your vertex and edge descriptors to be stable (never invalidated) then use listS or setS for the VertexList and OutEdgeList template parameters of adjacency_list.".

Beware that if you use adjacency_list<boost::listS,... you would likely need to make extra efforts to generate and update a property named vertex_index. Many algorithms will not work without it. See more details here https://stackoverflow.com/a/19758844/2876861

于 2014-10-11T03:07:09.197 回答