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
> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk