Re: [Boost-users] [Graph] dijkstra_shortest_paths color map

From: Doug Gregor (dgregor_at_[hidden])
Date: 2005-11-16 14:54:44

On Nov 15, 2005, at 12:53 PM, Daniel Mitchell wrote:

> I work with very large implicit graphs that use out-of-core storage for
> properties, including the vertex color property,

Very cool.

>  but the following bit of
> code in dijkstra_shortest_paths_no_init (boost-1.33.0) seems to 
> preclude the
> use of a custom color map.
>
> std::vector<default_color_type> color(num_vertices(g));
> default_color_type c = white_color;
> breadth_first_visit(g, s, Q, bfs_vis,
>   make_iterator_property_map(&color[0], index_map, c));
>
> What is the rationale for the above code, and how should I work around 
> it?

Well, I'd say that's a bug in dijkstra_shortest_paths_no_init, which 
should have a ColorMap template parameter. The best way to fix this 
would be to add a ColorMap parameter at the end, e.g., to turn 
dijkstra_shortest_paths_no_init into:

   template <class VertexListGraph, 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 VertexListGraph& g,
      typename graph_traits<VertexListGraph>::vertex_descriptor s,
      PredecessorMap predecessor, DistanceMap distance, WeightMap weight,
      IndexMap index_map,
      Compare compare, Combine combine, DistZero zero,
      DijkstraVisitor vis, ColorMap color);

Then just pass that color map through to the underlying 
breadth_first_search. For backward compatibility reasons, one would 
provide a helper function with the old signature  that creates that 
iterator_property_map and forwards to the new, more-parameterized 
version.

If you happen to make this change, I was greatly appreciate it if you 
would send it to the list so that we can incorporate it in future 
versions of the library. If we're quick, we can even get it into the 
upcoming 1.33.1 bug-fix release.

        Doug