CODEWITHSUNDEEP
c++c++11boostgraph-traversalboost-property-map
User1291
User1291

Reputation: 8182

BGL - BFS/DFS visitor, accessing vertex colours

In BGL, I can't quite figure out how to access the inherent colouring of the vertexes (white for untouched, grey for visited, black for finished) in a graph as they are visited during a bfs/dfs search.

Could somebody illustrate how to access a vertex' colour from within a dfs/bfs visitor? E.g. when writing a custom examine_edge?

Upvotes: 4

Views: 825

Answers (1)

sehe
sehe

Reputation: 392911

You forgot to include a SSCCE, so I'll sketch a prose answer:

You should use the vertex color map.

This is a property_map. In case of internal property maps, you can access property maps using get:

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

Now you can query the map using get:

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

However, most often the colormap will be external, so you can just give the visitor access to it:

Direct Access To External Property Map

In this example I chose to make the colormap itself a property of the visitor. I didn't choose the most efficient representation (map) but it

  • allows use without explicit initialization
  • is more generic because it works with non-integral vertex descriptors (e.g. when using listS instead of 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);
}

Prints

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 Internal Property

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

Prints

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

Shared Code

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

Upvotes: 7

Related Questions