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-07 05:27:54

Jeremiah Willcock wrote:
> 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.
> 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.
No, it would not work for me. In my case, I have to do a large number
(say 2000) of dijkstra shortest path calculations, then I do some
traffic modelling on them, and based on the results I need to go back to
the 2000 dijkstra's and resume them. Doing this in a visitor call-back
would (to my understanding) require a recursive approach where each
visitor, except number 2000, invokes another dijkstra + visitor. It
would probably be possible, but more complicated than my current
solution. I have considered putting the dijkstra calculations in
separate threads, but don't understand enought about threads to know if
it is acceptable to create 2000 threads on a desktop computer.

Another problem was that I run out of memory and one way of managing it
is to store the state of the dijkstra algorithm to hard disk after a
calculation and load the state from disk again upon resumption. This
requires me to explicitly know the state, and to be able to clear it and
overwrite it. This would not be possible in the thread solution, nor in
the recursion solution.
> Those would seem to be much simpler than what you're doing.
They would also be more correct. One problem with my solution is that it
introduces pseudo-edges from the source to the gray vertices. It works
fine for me because all my hooks are vertex-based. Edge-based hooks
however would need to know about the pseude-edges somehow in order to
ignore them.
> 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
It seems that the pair of functions: algorithm() and algorithm_no_init()
is ideal for resuming algorithms. The only caveat is that
algorithm_no_init() should live up to its name and not do any
initialization from scratch. It should be OK to initialize from
parameters that duplicate information, e.g. initialize the priority
queue from the color map.

It could entail the following:

Initialize Q from color map in dijkstra_shortest_paths_no_init() by
inserting the following after declaring Q

typedef typename property_traits<ColorMap>::value_type ColorValue;
typedef color_traits<ColorValue> Color;
typename graph_traits<VertexListGraph>::vertex_iterator vi, vi_end;
  for (tie(vi, vi_end) = vertices(g); ui != vi_end; ++vi)
    if(get(color, *vi) == Color::gray())

Call breadth_first_visit_no_init() instead of breadth_first_visit() from

Create breadth_first_visit_no_init() as a copy of breadth_first_visit(),
but remove the following lines.

put(color, s, Color::gray()); vis.discover_vertex(s, g);

Also it is no longer necessary to pass the source vertex argument.

If something along these lines could make it into the BGL that would be
great. I would like to make my work open source some time and it would
be great if it works seamlessly with boost at that point. For now, I can
tolerate overly complicated workarounds.

Alex Hagen-Zanker

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