BGL — посетитель BFS / DFS, доступ к цветам вершин

Вы забыли включить SSCCE, поэтому я набросаю прозаический ответ:

Вы должны использовать карту цветов вершин.

Это property_map. В случае внутренних карт свойств, вы можете получить доступ к картам свойств, используя get:

 property_map<boost::vertex_color_t, Graph>::const_type pmap =
boost::get(boost::vertex_color, g);

Теперь вы можете запросить карту, используя get:

 vertex_descriptor vd = /*some-function*/;
default_color_type color = boost::get(pmap, vd);

Однако чаще всего цветовая карта будет внешней, поэтому вы можете просто предоставить посетителю доступ к ней:

Прямой доступ к внешней карте недвижимости

В этом примере я решил сделать цветовую карту собственностью посетителя. Я не выбрал наиболее эффективное представление (карту), но оно

• позволяет использовать без явной инициализации
• является более общим, потому что он работает с нецелыми дескрипторами вершин (например, при использовании listS вместо vecS)

Жить на Колиру

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/graph_utility.hpp>

using namespace boost;

using Graph = adjacency_list<vecS, vecS, directedS>;

struct my_vis : default_dfs_visitor {
using colormap = std::map<Graph::vertex_descriptor, default_color_type>;
colormap vertex_coloring;

template<typename Vertex, typename Graph>
void discover_vertex(Vertex v, Graph const& g) {
default_color_type color = vertex_coloring[v];

default_dfs_visitor::discover_vertex(v,g);
}
};

int main() {
Graph const g = make();

my_vis vis;
depth_first_search(g, vis, make_assoc_property_map(vis.vertex_coloring));

for(auto& vc : vis.vertex_coloring)
std::cout << "vertex " << vc.first << " color " << vc.second << "\n";

print_graph(g);
}

Печать

vertex 0 color 4
vertex 1 color 4
vertex 2 color 4
vertex 3 color 4
vertex 4 color 4
0 --> 1 2
1 --> 0
2 --> 4
3 --> 1
4 --> 3

Использование внутреннего свойства

Жить на Колиру

using Graph = adjacency_list<vecS, vecS, directedS, property<vertex_color_t, default_color_type> >;

struct my_vis : default_dfs_visitor {
using colormap = property_map<Graph, vertex_color_t>::type;
colormap vertex_coloring;

template<typename Vertex, typename Graph>
void discover_vertex(Vertex v, Graph const& g) {
default_color_type color = vertex_coloring[v];
(void) color; // suppress unused warning

default_dfs_visitor::discover_vertex(v,g);
}
};

int main() {
Graph g = make();

my_vis::colormap map = get(vertex_color, g);
depth_first_search(g, my_vis{}, map);

for(auto u : make_iterator_range(vertices(g)))
std::cout << "vertex " << u << " color " << get(map, u) << "\n";

print_graph(g);
}

Печать

vertex 0 color 4
vertex 1 color 4
vertex 2 color 4
vertex 3 color 4
vertex 4 color 4
0 --> 1 2
1 --> 0
2 --> 4
3 --> 1
4 --> 3

Общий код

#include <boost/graph/graph_utility.hpp>

Graph make() {
Graph g;
add_vertex(g);
add_vertex(g);
add_vertex(g);
add_vertex(g);
add_vertex(g);
add_edge(0,1,g);
add_edge(0,2,g);
add_edge(1,0,g);
add_edge(2,4,g);
add_edge(4,3,g);
add_edge(3,1,g);

return g;
}