...

I would like to build a visitor that accesses the colour_map of a specific vertex. The idea is to 'hide' some vertices from the search completely.

The algorithm initializes the color map to white AFTER calling initialize_vertex. So your strategy won't work. Perhaps using filtered graph is a better option? If you wish to persevere with the current strategy, you could try to skip the initialization by using the dijkstra_shortest_path_no_init function, but be careful about also initializing the distance map and predecessor map yourself. Best wishes, Alex template <class Graph, class SourceInputIter, class DijkstraVisitor, class PredecessorMap, class DistanceMap, class WeightMap, class IndexMap, class Compare, class Combine, class DistZero, class ColorMap> inline void dijkstra_shortest_paths_no_init (const Graph& g, SourceInputIter s_begin, SourceInputIter s_end, PredecessorMap predecessor, DistanceMap distance, WeightMap weight, IndexMap index_map, Compare compare, Combine combine, DistZero zero, DijkstraVisitor vis, ColorMap color)

Hi Alex and all, Do you think its possible to do something in the 'discovery' phase of the visitor/search? Can I test in the discovery of a vertex and make it 'undiscoverable'/remove it from the search queue? Any ideas? Thanks

Hi Alex and all, Examine Vertex vis.examine_vertex(u, g) void This is invoked on a vertex as it is popped from the queue. This happens immediately before examine_edge() is invoked on each of the out-edges of vertex u. "Examine" seems to work once on first encounter (is that correct??) so might worth a try. I did try the code below but I got errors on the part the works with the color map. Any ideas? class dijkstra_2step : public boost::default_dijkstra_visitor { public: dijkstra_2step(std::vector<Weight> dists, double threshold): distances(dists), threshold(threshold) {} void examine_vertex(boost::graph_traits <unGraph>::vertex_descriptor u, const unGraph& g){ boost::property_map< unGraph, boost::vertex_color_t >::type colorMap = boost::get(boost::vertex_color, g); if( distances[u] > threshold ) colorMap[u] = boost::color_traits::black(); } std::vector<Weight> distances; double threshold; }; Thanks

From your link seem that I am in the same category of 'no_init' search so

Thanks Alex, Yes the m_distance in the visitor is the result of a previous search (not the current working one). A couple of questions. If I use my own colour map as you describe, Could I also colour it beforehand and not in the visitor? (the ones that are outside the cutoff will always be outside, this will not change during search) the colour map that I provide is used directly and its not 're-initialised'. What Im trying to achieve is to colour some vertices black so that the search will consider them "disconnected" and leave them with 'inf' distance. This also means that these vertices won't be part of any later computation inside the visitor, no relaxation etc (as an extension of what I have here: in a 'special brandes betweenness' visitor I could, theoretically at the moment, exclude them for the extra 'delta' calculations inside the visitor steps). Right? If Im missing something please let me know. Now the code. Im having treble building the correct 'no_init' call. Googling around helped but not much. Any ideas? Thanks std::vector<Vertex> predecessors(boost::num_vertices(m_ugraph)); std::vector<Weight> distances(boost::num_vertices(m_ugraph), std::numeric_limits<double>::max() ); IndexMap indexMap = boost::get(boost::vertex_index, m_ugraph); PredecessorMap predecessorMap(&predecessors[0], indexMap); DistanceMap distanceMap(&distances[0], indexMap); // What is the definition of the ColorMap if you use it outside a visitor? typedef typename boost::property_traits<ColorMap>::value_type color_type; typedef typename boost::color_traits<color_type> color_traits; std::vector<boost::default_color_type> colors(boost::num_vertices(m_ugraph)); boost::default_bfs_visitor vis; boost::graph_traits<unGraph>::vertex_iterator vertex_begin, vertex_end; for ( boost::tie(vertex_begin, vertex_end) = vertices(m_ugraph); vertex_begin != vertex_end; ++vertex_begin) { // color_traits::black() complains because of the problem above. if(old_distances[*vertex_begin] > radius1) boost::put(colors, *vertex_begin, color_traits::black()); } // My current call //boost::dijkstra_shortest_paths(m_ugraph, s_vertex, boost::weight_map(boost::get(&EdgeProperties::m_metric_distance_weight, m_ugraph)).predecessor_map(predecessorMap).distance_map(distanceMap)); // this is probably a mess! Im not at all sure dijkstra_shortest_paths_no_init(m_ugraph, s_vertex, predecessorMap, distanceMap, boost::weight_map(boost::get(&EdgeProperties::m_metric_distance_weight, m_ugraph)) , indexMap, std::less<Weight> , boost::closed_plus<Weight>, Weight(), vis, colors);

Hi Alex, Im getting there, thanks for your help. One thing that Im getting problems is the definition of the ColorMap. typedef boost::default_color_type Color; typedef boost::color_traits<Color> color_traits; typedef boost::shared_array_property_map<Color> ColorMap; ColorMap colorMap(boost::num_vertices(m_ugraph), indexMap); ### error: wrong number of template arguments (1, should be 2) In file included from /usr/include/boost/graph/named_function_params.hpp:25:0, from /usr/include/boost/graph/breadth_first_search.hpp:23, from ../graph.h:22, from ../graph.cpp:1: /usr/include/boost/property_map/shared_array_property_map.hpp:19:7: error: provided for 'template<class T, class IndexMap> class boost::shared_array_property_map' ../graph.cpp:1064:69: error: invalid type in declaration before ';' token ../graph.cpp:1065:70: error: expression list treated as compound expression in initializer [-fpermissive] ../graph.cpp:1065:70: error: cannot convert 'IndexMap {aka boost::vec_adj_list_vertex_id_map<VertexProperties, long unsigned int>}' to 'ColorMap {aka int}' in initialization ../graph.cpp:1089:44: error: no matching function for call to 'put(ColorMap&, boost::graph_traits<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProperties, EdgeProperties>

::vertex_descriptor&, Color&)'

###

Yes! thanks! That second argument at the array was the problem. If you are ever around central London Ill be happy to buy you a beer for all your help!