如何为Boost Graph Library的BFS遍历创建独立ColorMap？

我用(x,y,z)坐标标识3D晶格的每个单元格，单元格属性存在Cell类中。将Cell作为Boost Graph Library（BGL）的顶点对象，先构造空图，遍历所有单元格插入顶点，再根据邻域单元格的特定条件构建边。

需求是统计孤立连通单元格（簇）的数量，这是典型的广度优先搜索（BFS）场景，计划用BGL工具实现：遍历每个单元格，若未被访问且存在边，则遍历所有连通单元格，标记为同一簇并分配簇ID。

根据BGL文档，处理不连通组件需要多次BFS时，应使用breadth_first_visit()函数并自行初始化颜色。我选择了第二个重载版本：

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类中添加颜色属性，于是用std::map存储顶点描述符和颜色值的映射作为独立ColorMap：

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

图的构造代码可正常运行，邻接表打印验证正确，但调用breadth_first_visit()时编译失败。排查发现ColorMap需符合Boost Property Map规范，求解决方案。

感谢@sehe提供的自定义ColorMap示例。

BGL的breadth_first_visit()要求ColorMap必须符合Property Map概念，直接传入std::map无法满足要求，因为BGL需要通过Property Map的标准接口（如get()、put()函数）来访问和修改值。可以通过以下方式解决：

方法1：用boost::associative_property_map适配std::map #

Boost提供了associative_property_map模板，专门用来适配std::map这类关联容器，使其符合Property Map规范。修改代码如下：

#include <boost/property_map/associative_property_map.hpp>

// ...

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;
}

// 将std::map包装为符合规范的Property Map
boost::associative_property_map<std::map<Test002VertexDescriptor, boost::default_color_type>> color_map_wrapper(colour_map);

buffer<Test002VertexDescriptor> buffer;

// 传入包装后的Property Map
breadth_first_visit(graph, *graph.vertex_set().begin(), buffer, Test002_BFS_Visitor<Test002Graph>(), color_map_wrapper);

方法2：用boost::vector_property_map（适用于顶点描述符为整数的场景） #

如果你的顶点存储方式是vecS（此时顶点描述符为整数类型），可以使用vector_property_map，它的性能比std::map更优：

#include <boost/property_map/vector_property_map.hpp>

// ...

// 获取顶点总数
size_t vertex_count = boost::num_vertices(graph);
boost::vector_property_map<boost::default_color_type> color_map(vertex_count);

// 初始化所有顶点颜色为white_color
boost::fill(color_map, boost::default_color_type::white_color);

buffer<Test002VertexDescriptor> buffer;

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

简化方案：直接使用connected_components()统计连通分量 #

如果只是为了统计连通簇的数量，无需手动实现多次BFS，BGL提供了现成的connected_components()函数，代码更简洁：

#include <boost/graph/connected_components.hpp>

// ...

std::vector<int> component_ids(boost::num_vertices(graph));
int cluster_count = boost::connected_components(graph, &component_ids[0]);

// cluster_count即为所求的连通簇数量

内容的提问来源于stack exchange，提问作者Victor Tsang