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