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-02 05:59:43

>> 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.

>>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).
>> 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).

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

Alex Hagen-Zanker

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