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-02 15:42:37

On Fri, 2 Jul 2010, Alex Hagen-Zanker wrote:

>>> It appears that dijkstra_shortest_paths assumes that it will create the 
> color map, rather than you creating it. 
> That's what it looks like, but is not what I'd expect from the documentation. 
> Also it means that the named parameters variant behaves differently from the 
> plain variant.

OK.

>>> Is there a reason you need your own?
>
> Yes, what I really want is to interupt the algorithm once a criterion is met. 
> For instance all vertices within a given distance are found, or all vertices 
> from a list of targets are found. Then, I want to do further computations 
> (traffic modelling) on the black vertices only.  Finally, I would like to be 
> able to resume the interupted algorithm, but that is a spearate matter (and I 
> am starting to think that to solve that neatly, I will need to use 
> breath_first_search() directly, because that allows specifying the priority 
> queue as well).

That will be nasty, but will probably work (assuming you get the priority 
queue and visitor code correct; it is complicated).  You might want to 
also try dijkstra_shortest_paths_no_color_map(), although you would still 
need to hack out the queue creation code.  Another way to do things is to 
do the traffic modeling within your visitor; returning from the visitor 
then continues the algorithm.

>>>  If you want to know whether vertices have been visited, check their 
> distances against the infinity value that you passed in to the algorithm.
>
> Thanks, it's a good tip, but not exactly what I need. It would tell me which 
> veritces have been visited, but not whether their distance value is tentative 
> (gray vertices) or final (black vertices).

One way to do that is to hook examine_vertex(); anything whose distance is 
less than or equal to the distance of the vertex being examined is final. 
Since your description suggest that you are doing that hook anyway to know 
when to stop, finding black vertices is easy even without a color map.

> My workaround is to not use named parameters. It makes the code less concise, 
> but the results are correct.
>
> I replaced the following:
>
> boost::dijkstra_shortest_paths<TSubGraph, TVisitor >(
>   graph,  source,
>   boost::predecessor_map( &predecessors[0] )
>   .distance_map( &distances[0] )
>   .visitor( visitor )
>   .color_map( &colors[0])
> );
>
> With this:
>
> boost::dijkstra_shortest_paths<TSubGraph, TVisitor >(
>   graph, // Graph&
>   source  // vertex_descriptor s,
>   &predecessors[0], // PredecessorMap
>   &distances[0], // DistanceMap,
>   boost::get(boost::edge_weight, graph), // WeightMap 
> boost::get(boost::vertex_index, graph), // VertexIndexMap
>   std::less<double>(), // CompareFunction
>   boost::closed_plus<double>(), // CombineFunction
>   std::numeric_limits<double>::max(), // DistInf
>   (double) 0.0, // DistZero
>   visitor, //  DijkstraVisitor
>   &colors[0] // ColorMap
> );

That is complicated, and adding your own priority queue will make it even 
worse.  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.

-- Jeremiah Willcock