我的要求是拥有一个图结构,其中每个顶点都由 boost::uuids::uuid
唯一标识。 。所有顶点都有一个颜色属性,相似类别的顶点将根据该属性进行分组。我不是在处理静态 map ,顶点和边将动态创建和删除。
typedef boost::adjacency_list<
boost::listS,
boost::listS,
boost::bidirectionalS,
boost::property<boost::vertex_index_t, boost::uuids::uuid,
boost::property<boost::vertex_color_t, resource_color,
boost::property<boost::vertex_underlying_t, boost::shared_ptr<actual_object*> > > >,
detail::edge_property
> graph_type;
graph_type _graph;
boost::property_map<graph_type, boost::vertex_index_t>::type _index_map;
boost::property_map<graph_type, boost::vertex_color_t>::type _color_map;
boost::property_map<graph_type, boost::vertex_underlying_t>::type _underlying_map;
在构造函数中,我正在创建所有 3 张 map
_index_map = boost::get(boost::vertex_index_t(), _graph);
_color_map = boost::get(boost::vertex_color_t(), _graph);
_underlying_map = boost::get(boost::vertex_underlying_t(), _graph);
在添加顶点时
add_resource(resource_color c, actual_object* o){
graph_type::vertex_descriptor v = boost::add_vertex(o->uuid(), _graph);
_color_map[v] = c;
_underlying_map[v] = o;
}
用于列出顶点的 UUID
uuid_list list;
boost::graph_traits<graph_type>::vertex_iterator vi, vi_end;
for(boost::tie(vi, vi_end) = boost::vertices(_graph); vi != vi_end; ++vi){
list.push_back(_index_map[*vi]);
}
return list;
这样我总是迭代图的顶点并获取其属性。不过我也想要另一种方式。从 UUID 到顶点,就像并行 std::map 一样,它将通过添加/删除操作或类似的操作自动更新。
此外,我无法保留外部 std::map
并手动同步,因为boost::adjacency_list<boost::listS, boost::listS>::vertex_descriptor
计算结果为 void*
我需要序列化支持。
以下事情是否可行
- 通过
boost::vertex_index_t
查找顶点值 - 迭代
boost::property_map
- 正在同步外部
std::map
或bimap
与index
属性(property)
最佳答案
我记得该库有一个labeled_graph
实用程序大致支持这一点。它具有很高的便利性,但我似乎记得它在效率方面不太有趣。应该有一个使用它的示例:
无论如何(并引用您之前的问题)您当然可以使用外部属性映射。这样做有好处:
- 您可以始终保留不在图表中的条目
您可以拥有所需的反向索引,请参阅例如
Cut set of a graph, Boost Graph Library (它用于获取颜色图的反向查找)。
It also contains an equivalent approach but using Boost Multi-index Containers, which is much more flexible even
答案要点:
-
find vertex through
boost::vertex_index_t
value是的,但如果你想 boost 效率,确实需要有一个用于反向查找的外部映射或使用你自己的数据结构并将其适应 model the Graph Concepts you require (显然还有更多的工作)
-
iterate through a
boost::property_map
你可以。使用 boost::get(tag, graph) 获取属性映射,迭代您要访问的所有实体并调用每个属性的属性映射。例如
boost::property_map<Graph, boost::vertex_index_t>::type pmap = boost::get(boost::vertex_index, graph); boost::graph_traits<Graph>::vertex_iterator b, e; for (boost::tie(b,e) = boost::vertices(graph); b!=e; ++b) std::cout << "The vertex ID is: " << boost::get(pmap, *b) << "\n";
-
synchronizing an external
std::map
orbimap
withindex
property上面的链接应该会给你一些想法
¹ 这可以解释我自己没有使用过它。
关于c++ - BGL 通过键索引顶点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32296206/