Boost logo

Boost :

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
3. Don't take the source vertex as a parameter in breadth_first_search()
4. Add the priority queue as a parameter for
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

Boost list run by bdawes at, gregod at, cpdaniel at, john at