c++ - BGL 通过键索引一个顶点

Question

我的要求是有一个图形结构，其中每个顶点都由 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;

在 constructor 我正在创建所有 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*我需要序列化支持。

那么下面的事情是否可行

1. 通过boost::vertex_index_t找到顶点值(value)
2. 遍历 boost::property_map
3. 同步外部 std::map或 bimap与 index属性(property)

Answer 1

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

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

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

• 您可以始终保留不在图表中的条目

• 您可以拥有所需的反向索引，例如参见

  • 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

答案要点:

1. find vertex through boost::vertex_index_t value

   是的，但是如果你想 boost 效率，确实你需要有一个外部映射来进行反向查找或者使用你自己的数据结构并使其适应model the Graph Concepts you require (显然还有更多的工作)

2. 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";
   

3. synchronizing an external std::map or bimap with index property

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

---

¹ 这可以解释我自己还没有使用过它。