BGL — посетитель BFS / DFS, доступ к цветам вершин
В BGL я не могу понять, как получить доступ к внутренней окраске вершин (белый для нетронутого, серый для посещенного, черный для готового) в графе, когда они посещаются во время поиска bfs / dfs.
Может ли кто-нибудь проиллюстрировать, как получить доступ к цвету вершины из посетителя dfs / bfs? Например. при написании кастома examine_edge?
Решение
Вы забыли включить 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;
}
Другие решения
Других решений пока нет …