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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-07-06 18:43:52

On Tue, 6 Jul 2010, Alex Hagen-Zanker wrote:

> The problem of resuming a dijkstra_shortest_path calculation is solved and I 
> thought to share the solution here.
>
> It works now without making a copy of the input graph and without permanently 
> modifying the graph as I wrote earlier.
>
> The color map is used to make a list of gray vertices (i.e. those vertices in 
> the queue). Before resuming using dijkstra_shortest_path_no_init edges are 
> inserted that connect the source to the gray vertices (i.e. they will be 
> lined up to be put in the queue again). The distance of these edges is the 
> same as the vertex distance of the gray vertices. Subsequently the gray 
> vertices are colored white (i.e. marked as if not in the queue yet).
>
> The effect of these actions is that the gray vertices will be inserted into 
> the priority queue by the breadth_first_visit() at their appropriate 
> distance.
>
> After the dijkstra_shortest_path_no_init, it is necessary to clean up the 
> introduced edges. There is some overhead to deal with the case that there are 
> already edges between the gray vertices and the origin. Also there is some 
> overhead to make sure that tentative distances and predecessors are not 
> retained, but that is not essential.
>
> My code is below, it is not as generic as the BGL though.

That seems like it's a complicated workaround.  Did the ideas of just 
doing your work in a Dijkstra visitor callback (and the algorithm then 
resuming automatically) or using a separate thread not work for you? 
Those would seem to be much simpler than what you're doing.  Otherwise, we 
don't have a good way to resume algorithms, although it has been on the 
TODO list for a long time.  I might be able to put something simple 
together for you that works more directly for resumption.

-- Jeremiah Willcock