BGL dijksra_shortest_path and boost::on_initialize_vertex
Hello, I have my own graph model and want to run dikstra_shortest_path on it. I want a dijkstra_visitor to initialize the id's of my vertices, struct initialize_index : public boost::base_visitor<initialize_index> { int i; typedef boost::on_initialize_vertex event_filter; initialize_index(int i_) : i(i_) {} template <class Vertex, class Graph> void operator()(Vertex v, Graph& G) { std::cout << "i = " << i << std::endl; v->id() = i++; } }; . . . . 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 ? Shouldbn't it be called by the bfs performed in dijkstra_shortest_paths_no_init ? 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 ... andreas
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());
participants (2)
-
Andreas Fabri -
Douglas Gregor