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

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

直接访问外部属性地图

在这个例子中，我选择使颜色图本身成为访问者的 属性。我没有选择最有效的表示（地图），但它

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