首页 文章

Boost Graph标识顶点

提问于
浏览 次
2

我需要将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？

performance boost boost-graph

1 回答

  • 2

    当图形为 adjacency_list<boost::vecS, boost::vecS, ... 时，顶点描述符是整数 . 删除顶点时，某些顶点描述符可能会变为无效;类似地，删除边时，某些边描述符将变为无效 . 如果您从不删除图元素，则这些整数描述符仍然有效 .

    正如BGL文档所述，“如果您希望顶点和边缘描述符稳定（从未失效），则使用listS或setS作为adjacency_list的VertexList和OutEdgeList模板参数 . ”

    请注意，如果您使用 adjacency_list<boost::listS,... ，您可能需要额外努力来生成和更新名为vertex_index的属性 . 没有它，许多算法将无法工作 . 在这里查看更多详情https://stackoverflow.com/a/19758844/2876861

    回复于

相关问题