Boost Graph initialize_vertex change vertex color (visitor)

Question

I would like to build a visitor (for dikstra) with the initialise_vertex acting as 'colour map' modifier. I want to exclude some vertices from the search based on a condition. So I want to set some vertices 'black' in the init part of the algorithm.

class dijkstra_2step : public boost::default_dijkstra_visitor
{
     public:
        dijkstra_2step(std::vector<Weight> dists, double threshold): distances(dists), threshold(threshold) {}

// THIS PART IS NOT CORRECT!!!! //
        void initialize_vertex(boost::graph_traits <unGraph>::vertex_descriptor u, const unGraph& g){
             if( distances[u] > threshold ) color[u] = black; // ??????
        }
//////////

     std::vector<Weight> distances;
     double threshold;
};

Any help for the above visitor? How to I access the colour map? I couldn't find something online.

Michael Simbirsky · Accepted Answer · 2017-04-19T18:26:36.920

1

What you want is probably the follows:

In the case of Dijkstra you can actually pass an arbitrary container (e.g. std::map or even std::vector) as a color map; you just need to wrap it properly:

  #include "boost/graph/properties.hpp"   
  std::vector<int> colorMap(num_vertices(g), boost::white_color);

After that you can mark some vertices as "black" in this container. Then you have to call dijkstra_shortest_paths_no_init variant of Dijkstra.

 dijkstra_shortest_paths_no_init(g, src, ..., ..., &colorMap[0]);

Just for the record, a standard way to get a color map is with code like

boost::property_map< unGraph, boost::vertex_color_t >::type colorMap =
            boost::get(boost::vertex_color, g);

(provided such map is defined for given graph type).

BTW, alternatively, you can use filtered_graph as your input instead of unGraph; you will have to provide a vertex filter which specifies which vertices are in the graph.

edited Apr 19 '17 at 18:26

answered Jan 14 '14 at 21:53

Michael Simbirsky

3,045
1
12
24

Regarding the colour map: Every search has one right? Do I need to define it somewhere? Maybe Im missing something? – OHTO Jan 20 '14 at 11:59
Yes, all search graph algorithms use some color map. Look at documentation, usually search has a param for `UTIL/OUT: color_map(ColorMap c_map)`. It means you can provide your own. If you do not, BGL will create a temporary one. – Michael Simbirsky Jan 20 '14 at 23:07
In what header is `boost::color_white` defined ? Can't find it. – kebs Apr 18 '17 at 15:42
1

@kebs, thanks for paying my attention for the typo. It is `white_color`, not `color_white`. It is defined in graph/properties.hpp. You do not have to use it, can also make your own color `enum { color_white, color_black, color_grey }` anywhere in your code, even in anonymous namespace. – Michael Simbirsky Apr 19 '17 at 18:21
See my mail thread years ago http://boost.2283326.n4.nabble.com/BGL-dijkstra-shortest-paths-with-listS-td2557281.html – gast128 Apr 19 '17 at 18:30
1

Thanks, I was trying to set up a property map with the help of your answer and couldn't get rid of that error. (I finally initialized the vector with 0). – kebs Apr 19 '17 at 22:02

Boost Graph initialize_vertex change vertex color (visitor)

1 Answers1

Linked