我有一个用以下实例化的图形:
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中直接访问,这种方法可以工作,但会增加这个映射开销。
我可以以某种方式指定自定义索引或在BGL中获取/放置顶点时要比较的内容吗?或者将顶点描述符保留在地图中是最好的方法吗?
coliru的完整示例
简短回答:是的。
笔记:
labeled_graph<>
适配器。我相信它用在库样本中,也是我have a number of answers using it on this site(免责声明:我也发现了一些错误,所以YMMV)add_vertex
助手没有被使用,即使你写了:
const auto vd = add_vertex(i, g);
小心ADL!你将函数命名为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
替换循环以打印图形#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