[BGL] dijkstra_shortest_path fails to call initialize_vertex
In Boost 1.33.1, the documentation at http://boost.org/libs/graph/doc/dijkstra_shortest_paths.html for the Dijkstra's Shortest Path algorithm says that the initialize_vertex(v,g) method of a Dijkstra visitor is invoked on each vertex in the graph before the start of the algorithm, but when I created a visitor with an initialize_vertex method, it was never called. I did some digging into the source, and found that when the Dijkstra's algorithm delegates to the Breadth First Search algorithm, it calls breadth_first_visit. However, only breadth_first_search calls initialize_vertex. Thus initialize vertex is never called. For now, I've decided to work around it without patching BGL, but can this be fixed in a future version?
On Aug 9, 2006, at 12:07 AM, Michael Barrientos wrote:
I did some digging into the source, and found that when the Dijkstra's algorithm delegates to the Breadth First Search algorithm, it calls breadth_first_visit. However, only breadth_first_search calls initialize_vertex. Thus initialize vertex is never called.
Yep, you're right.
For now, I've decided to work around it without patching BGL, but can this be fixed in a future version?
It's been fixed for 1.34.0. Doug
Hello, By the way, isn't it rather undesirable that initialisation is done prior to the algorithm, rather than on-demand? I once had the idea of using boost::graph to implement a diffing algorithm by applying dikstra to the edit graph of two sequences (that's the popular way of doing this I think). But you don't really want to build that graph, or you'll end up with quadratic complexity in any case, whereas you can have something like O(kn) where n is the length of both sequences and k is the number of "edits" in a shortest ed-script (if we take the priority queue lookup as constant). There are probably other applications where it also matters. In my case, the quadracticness doesn't really matters much. Cheers, Jens
On Aug 9, 2006, at 5:20 PM, Jens Theisen wrote:
By the way, isn't it rather undesirable that initialisation is done prior to the algorithm, rather than on-demand?
I once had the idea of using boost::graph to implement a diffing algorithm by applying dikstra to the edit graph of two sequences (that's the popular way of doing this I think).
I didn't know that. Very interesting!
But you don't really want to build that graph, or you'll end up with quadratic complexity in any case, whereas you can have something like O(kn) where n is the length of both sequences and k is the number of "edits" in a shortest ed-script (if we take the priority queue lookup as constant).
There is a "no_init" version of Dijkstra's algorithm that skips the initialization entirely. Of course, the user would be responsible for initializing property map values for vertices on demand, e.g., in examine_edge. I've seen the no_init form of Dijkstra's used for other "implicit" graphs, which have similar properties to the one you describe. Doug
Doug Gregor wrote:
I once had the idea of using boost::graph to implement a diffing algorithm by applying dikstra to the edit graph of two sequences (that's the popular way of doing this I think).
I didn't know that. Very interesting!
Well, sorry, I meant viewing it as finding the shortest path in the edit graph is popular. Rooting in on dijkstra itself probably isn't.
There is a "no_init" version of Dijkstra's algorithm that skips the initialization entirely. Of course, the user would be responsible for initializing property map values for vertices on demand, e.g., in examine_edge. I've seen the no_init form of Dijkstra's used for other "implicit" graphs, which have similar properties to the one you describe.
That doesn't help very much because even that is initialising it's relaxed_heap with num_vertices(g), so the algorithm will linear in the number of it's vertices anyway. You really want to drop the VertexListGraph requirement for the no_init version (or yet another one). Jens
On Aug 10, 2006, at 3:27 PM, Jens Theisen wrote:
Doug Gregor wrote:
There is a "no_init" version of Dijkstra's algorithm that skips the initialization entirely. Of course, the user would be responsible for initializing property map values for vertices on demand, e.g., in examine_edge. I've seen the no_init form of Dijkstra's used for other "implicit" graphs, which have similar properties to the one you describe.
That doesn't help very much because even that is initialising it's relaxed_heap with num_vertices(g), so the algorithm will linear in the number of it's vertices anyway. You really want to drop the VertexListGraph requirement for the no_init version (or yet another one).
You are absolutely correct. I've opened up a bug report here: http://sourceforge.net/tracker/index.php? func=detail&aid=1540116&group_id=7586&atid=107586 I'll try to fix it in the near future, but it will likely take me a week or two before I get to it. Doug
Doug Gregor wrote:
On Aug 9, 2006, at 12:07 AM, Michael Barrientos wrote:
I did some digging into the source, and found that when the Dijkstra's algorithm delegates to the Breadth First Search algorithm, it calls breadth_first_visit. However, only breadth_first_search calls initialize_vertex. Thus initialize vertex is never called.
Yep, you're right.
For now, I've decided to work around it without patching BGL, but can this be fixed in a future version?
It's been fixed for 1.34.0.
Doug
Reminder to self for the future: check the CVS to see if it's already fixed in the next release. However, it's not fixed the way I had hoped it would be. I had hoped that the fix would place the initialize_vertex call after the initialization of the color/distance/predecessor maps, like it is in 1.33.1 for BFS. I noticed that the fix in CVS places the initialize call before the initialization, and that the BFS/Astar/etc. have similarly moved the initialize_vertex call to before the color map initialization. What I'm trying to do (which I admit is very non-standard) is to set the color of vertices that I do not want visited to black on graph initialization. My visitor would have access to an external color map, and sets the vertex color to black during initialize_vertex. The way it is now, the vertex color is unconditionally set to white after the initialize_vertex call, overwriting any changes I make. I know a similar thing can be accomplished by setting edge weights to infinite or by using a filtered graph, but both of these solutions end up costing more in performance because the function is called multiple times (the blacking out/filtering function is a pretty expensive operation). What are the chances of moving the initialize_vertex call to a point after the vertex color is initialized? Or will the only recourse be to call the internal function dijkstra_shortest_paths_no_init directly? -- Mike Barrientos - michael_barrientos@appsig.com
On Aug 9, 2006, at 7:45 PM, Michael Barrientos wrote:
Doug Gregor wrote:
On Aug 9, 2006, at 12:07 AM, Michael Barrientos wrote:
I did some digging into the source, and found that when the Dijkstra's algorithm delegates to the Breadth First Search algorithm, it calls breadth_first_visit. However, only breadth_first_search calls initialize_vertex. Thus initialize vertex is never called.
Yep, you're right.
For now, I've decided to work around it without patching BGL, but can this be fixed in a future version?
It's been fixed for 1.34.0.
Doug
Reminder to self for the future: check the CVS to see if it's already fixed in the next release. However, it's not fixed the way I had hoped it would be.
I had hoped that the fix would place the initialize_vertex call after the initialization of the color/distance/predecessor maps, like it is in 1.33.1 for BFS. I noticed that the fix in CVS places the initialize call before the initialization, and that the BFS/Astar/etc. have similarly moved the initialize_vertex call to before the color map initialization.
Unfortunately, the documented behavior has always been to call initialize_vertex first. We've had bugs in the implementation, but the documentation has been the same. I don't recall what prompted us to move the initialize_vertex call, but I expect it was due to some other user relying on an initial call to initialized_version :( I think you'll probably need to use the no_init version. Sorry! Doug
participants (4)
-
Doug Gregor -
Douglas Gregor -
Jens Theisen -
Michael Barrientos