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