代码之家 › 专栏 › 技术社区 › Victor Tsang

如何为Boost图库BFS访问制作一个简单的ColorMap?

boost-property-map boost-graph boost

Victor Tsang · 技术社区 · 1 年前

假设我有一个三维晶格,用它的坐标(x,y,z)和一个类来识别每个单元 Cell 保持其特性。我想把它用作BGL的顶点对象,首先构造一个空图,然后迭代每个单元,在相邻单元之间插入顶点并根据一些标准构建边。

现在,我想数一下有多少孤立的相互连接的细胞(簇)。说这是一个典型的面包优先搜索问题。人们告诉我要学习BGL,因为它是图形/晶格研究的工具箱。。。

我的高级思想是遍历每个单元,如果它没有被访问并且有边缘,遍历所有连接的单元,将它们标记为集群并分配集群ID。

这个 doc 说

如果需要对图形执行多个广度优先搜索(例如,如果有一些断开连接的组件),请使用breadth_first_visit()函数并进行自己的颜色初始化。

因此,我转向breadth_first_visit()。它有两种变体:

template <class IncidenceGraph, class P, class T, class R>
  void breadth_first_visit(IncidenceGraph& G,
    typename graph_traits<IncidenceGraph>::vertex_descriptor s,
    const bgl_named_params<P, T, R>& params);

  template <class IncidenceGraph, class Buffer, class BFSVisitor, class ColorMap>
  void breadth_first_visit
    (const IncidenceGraph& g,
     typename graph_traits<IncidenceGraph>::vertex_descriptor s,
     Buffer& Q, BFSVisitor vis, ColorMap color)

由于我不想在Cell类中添加color属性,所以我想设置一个独立的 ColorMap 这个 Buffer 和 BFSVisitor 看起来很简单。

对于ColorMap,我尝试准备一个std::map<顶点描述符,颜色值>白色地图:

  struct Test002Vertex;
  using Test002Graph=boost::adjacency_list<boost::vecS, boost::listS,boost::undirectedS,Test002Vertex>;
   using Test002GraphTraits=boost::graph_traits<Test002Graph>;
  // same as Test002Graph::vertex_descriptor
  using Test002VertexDescriptor=Test002GraphTraits::vertex_descriptor;

  // implement Buffer concept
  // https://www.boost.org/doc/libs/1_85_0/libs/graph/doc/Buffer.html
  template<typename T,typename Container=std::deque<T>>
  class buffer
 { ... }

...


    // user defined colour map
    std::map<Test002VertexDescriptor,boost::default_color_type> colour_map;
    for(auto const &v:graph.vertex_set())
    {
      colour_map[v]=boost::default_color_type::white_color;
    }


    buffer<Test002VertexDescriptor> buffer;

    breadth_first_visit(graph,*graph.vertex_set().begin(),buffer,Test002_BFS_Visitor<Test002Graph>(),colour_map);

代码可以构建图形,并打印相邻列表以验证其正确性。

下一步是进行BFS遍历。。。它在breath_first_visit()中编译失败。

仔细查看细节,发现 颜色贴图 实际上是一个提升属性映射库!!又是一个大障碍。属性映射库的文档似乎比BGL更糟糕:~(

谢谢@sehe在下面的评论中展示了一些用户定义的颜色图的例子。

1 回复 | 直到 1 年前

sehe 1 年前

当你有

std::map<Test002VertexDescriptor, boost::default_color_type> colour_map;

您必须将其调整为属性映射以满足 the required concept :

类型ColorMap必须是的模型 Read/Write Property Map 并且其键类型必须是图形的顶点描述符类型,并且颜色映射的值类型必须为ColorValue建模。

幸运的是,你只需拍打一下就能做到 make_assoc_property_map 在上面。

请注意,初始化循环是完全冗余的,因为的值初始化的默认值 default_color_type 已经等于 white_color (对应于整数枚举值 0 ).

Demo

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/buffer_concepts.hpp>
#include <iostream>
#include <stack>
using Test002Graph            = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
using Test002VertexDescriptor = Test002Graph::vertex_descriptor;

template <typename Graph> struct Test002_BFS_Visitor : public boost::default_bfs_visitor {
    template <typename Vertex> void discover_vertex(Vertex v, Graph const&) const { std::cout << "Discovered vertex " << v << std::endl; }
    template <typename Edge>   void examine_edge(Edge      e, Graph const&) const { std::cout << "Examining  edge   " << e << std::endl; }
    template <typename Edge>   void tree_edge(Edge         e, Graph const&) const { std::cout << "Tree       edge   " << e << std::endl; }
    template <typename Edge>   void non_tree_edge(Edge     e, Graph const&) const { std::cout << "Non-tree   edge   " << e << std::endl; }
    template <typename Edge>   void gray_target(Edge       e, Graph const&) const { std::cout << "Gray       target " << e << std::endl; }
    template <typename Edge>   void black_target(Edge      e, Graph const&) const { std::cout << "Black      target " << e << std::endl; }
    template <typename Vertex> void finish_vertex(Vertex   v, Graph const&) const { std::cout << "Finished   vertex " << v << std::endl; }
};

int main() {
    Test002Graph                                                 graph(1);
    std::map<Test002VertexDescriptor, boost::default_color_type> colour_map;

    for (auto v : boost::make_iterator_range(vertices(graph))) {
        colour_map[v] = boost::default_color_type::white_color;
    }
    std::stack<Test002VertexDescriptor> buffer;
    breadth_first_visit(graph, *graph.vertex_set().begin(), buffer, Test002_BFS_Visitor<Test002Graph>(),
                        make_assoc_property_map(colour_map));
}