如何制作一个简单的ColorMap供Boost Graph Library BFS访问？

Question

假设我有一个 3D 晶格，用坐标 (x,y,z) 标识每个单元，并且类

Cell

保存其属性。我想用它作为 BGL 的顶点对象，首先构建一个空图，然后迭代每个单元以插入顶点并根据邻域单元之间的某些标准构建边。

现在，我想计算有多少个孤立的互连单元（簇）。说这是一个典型的Bread-First-Search问题。人们告诉我学习 BGL，因为它是图/格研究的工具箱......

我的高级思维是遍历每个单元格，如果它未被访问并且有边缘，则遍历所有连接的单元格，将它们标记为簇并分配簇ID。

医生说

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

所以，我转向breadth_first_visit()。它有 2 个变体：

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 类中，所以我想设置一个独立的

ColorMap

。

Buffer

和

BFSVisitor

看起来很简单。

对于 ColorMap，我尝试准备一个 std::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);

但是编译失败。

仔细查看，发现

ColorMap

其实是一个boost属性图库！！另一个大阻碍。属性图库的文档看起来比BGL还差:~(

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

Answer 1

当你有

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

您必须将其改编为属性映射以满足所需的概念：

类型 ColorMap 必须是读/写属性映射的模型，其键类型必须是图的顶点描述符类型，并且颜色图的值类型必须是 ColorValue 的模型。

幸运的是，你只需拍

make_assoc_property_map

就可以了。

请注意，初始化循环是完全多余的，因为

default_color_type

的值初始化的默认值已经等于

white_color

（对应于积分枚举值

0

）。

演示

住在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));
}