BGL 通过键索引顶点

2021-12-24 00:00:00 c++ boost boost-graph

我的要求是有一个图结构，其中每个顶点都由 boost::uuids::uuid 唯一标识.所有顶点都有一个颜色属性，相似类别的顶点将根据该属性进行分组.我不是在静态地图上工作，顶点和边将被动态创建和删除.

My requirement is to have a graph structure where each vertex is uniquely identified by a boost::uuids::uuid. All vertices have a color property by which vertices of similar category will be grouped. I am not working on a static map, vertices and edges will be created and removed dynamically.

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 个地图

In constructor I am creating all 3 maps

_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，它将通过添加/删除操作或类似的东西自动更新.

This way i am always iterating through vertices of the graph and getting its properties. However I want the other way too. From UUID to vertex like a parallel std::map which will be auto updated with add/remove operations or somethign similar.

此外，我无法保留外部 std::map 并手动同步，因为 boost::adjacency_list<boost::listS, boost::listS>::vertex_descriptor计算结果为 void*，我需要序列化支持.

Also I cannot keep an external std::map and sync manually, because boost::adjacency_list<boost::listS, boost::listS>::vertex_descriptor evaluates to void* and I need serialization support.

以下是可行的

  1. 通过boost::vertex_index_t值查找顶点
  2. 遍历boost::property_map
  3. 将外部std::map 或bimap 与index 属性同步
  1. find vertex through boost::vertex_index_t value
  2. iterate through a boost::property_map
  3. synchronizing an external std::map or bimap with index property

推荐答案

我记得图书馆有一个 labeled_graph 实用程序，大致支持这个.它具有很高的便利性，我似乎记得它在效率方面不那么有趣1.应该有一个使用它的示例:

I remember the library has a labeled_graph utility that supports this roughly. It has a high convenience factor and I seem to remember it being less interesting in terms of efficiency1. There should be a sample using it:

  • http://www.boost.org/doc/libs/1_46_1/libs/graph/example/labeled_graph.cpp

无论如何(并参考您之前的问题)您当然可以使用外部属性映射.这有好处:

Regardless (and referring back to your previous question) you can certainly use an external property map. This has benefits:

  • 您可以随时保留不在图表中的条目

  • 你可以有你需要的反向索引，参见例如

  • you can keep entries that aren't in the graph at all times

  • you can have the reverse index that you require, see e.g.

  • 图的割集，Boost Graph Library(用于反向查找颜色图).

  • Cut set of a graph, Boost Graph Library (where it is used to get reverse-lookup of the colour map).

它还包含一个等效的方法，但使用 Boost Multi-index Containers，甚至更加灵活

It also contains an equivalent approach but using Boost Multi-index Containers, which is much more flexible even

通过boost::vertex_index_t值查找顶点

是的，但是如果您想提高效率，实际上您需要为反向查找使用外部映射或使用您自己的数据结构并使其适应为您需要的图概念建模(显然需要做更多的工作)

Yes, but if you want to be efficient, indeed you need to either have an external mapping for the reverse lookup OR use your own datastructure and adapt it to model the Graph Concepts you require (much more work, obviously)

遍历boost::property_map

你可以.使用 boost::get(tag, graph) 获取属性映射，遍历您要访问的所有实体并为每个属性调用属性映射.例如

You can. Use boost::get(tag, graph) to get the property map, iterate across all entities you want to visit and invoke the property map for each property. E.g.

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) << "
";

  • 将外部std::map 或bimap 与index 属性同步

    上面的链接应该会给你一些想法

    The above links should give you ideas

    <小时>

    1 这可以解释我自己没有使用过它.

    1 that would explain I haven't used it myself.

    • 相关文章