c++ - 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 查询 map :

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

但是，大多数情况下颜色图是外部的，因此您可以只允许访问者访问它:

直接访问外部属性映射

在此示例中，我选择将颜色图本身作为访问者的属性。我没有选择最有效的表示( map )，但它

• 允许在没有显式初始化的情况下使用
• 更通用，因为它适用于非整数顶点描述符(例如，当使用 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 

使用内部属性

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