Re: [Boost-users] BGL dijksra_shortest_path and boost::on_initialize_vertex

From: Douglas Gregor (doug.gregor_at_[hidden])
Date: 2005-12-12 10:31:17

On Dec 8, 2005, at 9:25 AM, Andreas Fabri wrote:
> I want a dijkstra_visitor to initialize the id's of my vertices,
> [snip code]
> boost::dijkstra_shortest_paths(ft, source ,
>                   distance_map(distance_pmap)
>                   .predecessor_map(predecessor_pmap)
>                   .visitor(make_dijkstra_visitor(initialize_index 
> (0))));
>
>
>
> but the operator is never called.
>
> Is that a bug ?

Yep, it's a bug. The fix is quite simple (see the end of the  
message). This change will go into CVS in a few minutes.

>   Shouldbn't it be called by the bfs performed
> in dijkstra_shortest_paths_no_init ?

I think dijkstra_shortest_paths_no_init is correct; it calls  
breadth_first_visit which does not initialize its vertices.

> Also when looking in the header file dijkstra_shortest_paths.hpp
> I see that the color map gets initialized before the vertices
> get initialized.   I would expect that the vertices get initialized
> before the color map gets initialized, because if the vertex_index_map
> is not set up correctly ...

You're referring to breadth_first_search.hpp, I presume? You're  
right: it does make sense to call initialize_vertex before writing  
into property maps, to give the visitor the chance to act first. I've  
also made this change and will put it into CVS in a few minutes  
(waiting for regression tests to run).

Thanks for the report!

        Doug

Index: dijkstra_shortest_paths.hpp
===================================================================
RCS file: /cvsroot/boost/boost/boost/graph/dijkstra_shortest_paths.hpp,v
retrieving revision 1.42
diff -u -r1.42 dijkstra_shortest_paths.hpp
--- dijkstra_shortest_paths.hpp 8 Dec 2005 02:53:30 -0000       1.42
+++ dijkstra_shortest_paths.hpp 12 Dec 2005 15:24:21 -0000
@@ -108,8 +108,7 @@
        }
        template <class Vertex, class Graph>
-      void initialize_vertex(Vertex u, Graph& g)
-        { m_vis.initialize_vertex(u, g); }
+      void initialize_vertex(Vertex u, Graph& g) { }
        template <class Edge, class Graph>
        void non_tree_edge(Edge, Graph&) { }
        template <class Vertex, class Graph>
@@ -247,6 +246,7 @@
      typedef color_traits<ColorValue> Color;
      typename graph_traits<VertexListGraph>::vertex_iterator ui,  
ui_end;
      for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) {
+      vis.initialize_vertex(*ui, g);
        put(distance, *ui, inf);
        put(predecessor, *ui, *ui);
        put(color, *ui, Color::white());