我应该跟踪 boost 图形库中的顶点描述符吗？

Question

我有一个图实例化如下：

typedef boost::property<boost::edge_weight_t, uint32_t> EdgeWeightProperty;
typedef boost::property<boost::vertex_index_t, uint32_t> VertexProperty;
typedef boost::adjacency_list<boost::vecS, boost::setS,
                              boost::undirectedS, VertexProperty,
                              EdgeWeightProperty, boost::setS> Graph;

我需要更新这张图，例如添加或删除边缘。因为我使用集合来存储顶点，所以我不能使用它们的索引，但我可以保留一张地图：

unordered_map<uint32_t, Vertex_Descriptor>

将我的索引映射到顶点描述符，这样我以后就可以直接在 BGL 中访问，这种方法有效但增加了映射开销。

当 getting/putting BGL 中的顶点时，我能否以某种方式指定自定义索引或要比较的内容？或者在地图中保留顶点描述符是最好的方法？

完整示例位于 coliru

Answer 1

简短回答：是的。

备注：

考虑文档不足的 labeled_graph<> 适配器。我相信它在库示例中使用过，我也 have a number of answers using it on this site（免责声明：我还在其中发现了一些错误，所以 YMMV）
你自己的全局 add_vertex 助手没有被使用，即使你写了：
```
const auto vd = add_vertex(i, g);
```
提防日常生活习惯！您将函数命名为 add_vertex，除非您编写 (add_vertex)(i, g)，否则 ADL 会在 boost 中找到重载，因为 adjacency_list<> 来自该命名空间（以及其他相关类型）。

所以，你可以放弃你的辅助函数，仍然像使用 boost add_vertex 重载那样编写它属性: MutablePropertyGraph concept, under "Valid Expressions":
```
for (int i = 0; i < 10; ++i)
     id_vertex[i] = add_vertex(i, g);
```
同时替换循环以打印您可以使用的图表 print_graph

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <iostream>

typedef boost::property<boost::vertex_index_t, uint32_t> VertexProperty;
typedef boost::property<boost::edge_weight_t, uint32_t> EdgeWeightProperty;
typedef boost::adjacency_list<boost::vecS, boost::setS, boost::undirectedS, VertexProperty, EdgeWeightProperty,
                              boost::setS> Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
typedef boost::graph_traits<Graph>::vertex_iterator vertex_it;

int main() {
    Graph g;
    std::unordered_map<uint32_t, Vertex> id_vertex;

    for (int i = 0; i < 10; ++i)
        id_vertex[i] = add_vertex(i, g);

    std::pair<vertex_it, vertex_it> vp;
    for (int i = 0; i < 9; ++i)
        add_edge(id_vertex[i], id_vertex[i + 1], g);

    clear_vertex(id_vertex[2], g);
    remove_vertex(id_vertex[2], g);

    print_graph(g);
}

版画

0 <--> 1 
1 <--> 0 
3 <--> 4 
4 <--> 3 5 
5 <--> 4 6 
6 <--> 5 7 
7 <--> 6 8 
8 <--> 7 9 
9 <--> 8

我应该跟踪 boost 图形库中的顶点描述符吗？

should I keep track of vertex descriptors in boost graph library?

c++

boost

boost-graph