How to make a simple ColorMap for Boost Graph Library BFS visit?

Suppose I have a 3D lattice, identify each cell with its coordinates (x,y,z), and a class Cell holds its properties. I want to use it as the vertex objects of BGL, first to construct an empty graph, then iterate each cell to insert vertexes and build edges upon some criteria among the neighborhood cells.

Now, I want to count how many isolated interconnected cells (clusters). Said that it is a typical Bread-First-Search problem. People tell me to learn BGL since it is a toolbox for graph/lattice research...

My high level thinking is to go through every cell, if it is not visited and has edge(s), traverses all the connected cells, mark them as a cluster and assign a cluster ID.

The doc said

If you need to perform multiple breadth-first searches on a graph (for example, if there are some disconnected components) then use the breadth_first_visit() function and do your own color initialization.

So, I turn to breadth_first_visit(). It has 2 variants:

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)

since I don't want to add color property into the Cell class, I want to set up a standalone ColorMap. The Buffer and BFSVisitor looks straightforward.

For the ColorMap, I try to prepare a std::map<vertex_descriptor, ColorValue> white 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);

The code is okay to construct the graph, and printed the adjancency lists to verify to correctness.

The next step is to do BFS traversal... it failed to compile in the breadth_first_visit().

Looked into the details, found that the ColorMap is in fact a boost Property Map Library!! Another big blocker. The documentation of the property map library seems even more worse than BGL :~(

Thanks @sehe in the comments below showed some examples for user defined color map.

Solution

When you have

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

You have to adapt it as property map to satisfy the required concept:

The type ColorMap must be a model of Read/Write Property Map and its key type must be the graph's vertex descriptor type and the value type of the color map must model ColorValue.

Luckily, you can do it by just slapping make_assoc_property_map on it.

Note that the initialization loop is completely redundant because the default value on value-initialization for default_color_type is already equal to white_color (corresponding to the integral enum value 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));
}