Re: [boost] Boost Graph Library: Dijkstra Shortest Path ignores color_map in named parameters?

Subject: Re: [boost] Boost Graph Library: Dijkstra Shortest Path ignores color_map in named parameters?
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2010-07-05 06:06:14

 >>If you think the things I suggested above aren't enough, I am willing 
to adapt the algorithm so that you can have your own color map and/or 
queue, even in the named parameter versions.

Your suggestions fully take care of the problem of the color_map, thank 
you very much.

For the problem of resuming, I now employ another solution that is not 
very elegant; I make a copy of the graph that I am working on and delete 
from it all the edges between black cells, while inserting edges from 
the origin to the gray cells with the appropriate distance. I am making 
a superfluous copy of my graph and create too many overheads and 
complications. It works now, but I think it would still be very useful 
if BGL could offer better support for resuming calculations.

The function dijkstra_shortest_path_no_init() seems to be ideal for the 
purpose of resuming an interrupted dijkstra_shortest_path(). I see some 
issues that would need to be addressed:

(1) The priority queue should not be initialized from scratch in 
dijkstra_shortest_path_no_init(). It could possibly be initialized from 
the color map or be supplied be the user as a parameter.

(2). The source vertice is a parameter to 
dijkstra_shortest_path_no_init(). The source vertex only seems relevant 
to the initialization. It is a clue for the initialization of the 
distance map (d[s] = 0), the color map (c[s] = gray), and the priority 
queue (Q.assign(1, s)).

(3) The same problem goes for the breadth_first_visit(). It is 
contradictary to supply both the initialized priority queue and the 
source vertex, because the source vertex is used to initialize the 
queue. It is not correct to start the breadth_first_visit by inserting 
the source vertex  into the queue map and coloring it gray. (it could be 
black already). In practice it might not be much of an issue as 
processing the source vertex one more time is not too costly, but still 
it could be cause for errors.

My proposed solution:

1. Initialize the priority queue already in dijkstra_shortest_path()
2. Don't take the source vertex as a parameter in 
dijkstra_shortest_path_no_init()
3. Don't take the source vertex as a parameter in breadth_first_search()
4. Add the priority queue as a parameter for 
dijkstra_shortest_path_no_init()
5. Provide helper functions to initialize a priority queue from: (a) 
single source vertex (b) color_map + distance_map.

I know I see these issues from my particular user-perspective, so please 
take the "should's", "must's", "issues", and "incorrect's" with a grain 
of salt.
--
Alex Hagen-Zanker
 
-- 
Alex Hagen-Zanker