BGL - BFS/DFS访问者,访问顶点颜色

Question

在BGL中,我无法弄清楚如何在bfs/dfs搜索期间访问图中的顶点的固有颜色(白色表示未触摸,灰色表示已访问,黑色表示完成).

有人可以说明如何从dfs/bfs访问者中访问顶点颜色吗？比如写自定义examine_edge？

Answer 1

你忘了加入一个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);

但是,通常色彩映射图是外部的,因此您只需让访问者访问它:

直接访问外部属性映射

在这个例子中,我选择使colormap本身成为访问者的一个属性.我没有选择最有效的表示(地图),但它

• 允许在没有显式初始化的情
• 更通用,因为它适用于非整数顶点描述符(例如,当使用listS而不是vecS)时

Live On Coliru

#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 

使用内部属性

住在Coliru

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