Boost logo

Boost :

Subject: [boost] Boost Graph Library: Dijkstra Shortest Path ignores color_map in named parameters?
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2010-07-01 12:18:37

I am trying to use the dijkstra_shortest_path algorithm with named
parameters. It worked well, until I wanted to pass the color map as an

Despite providing my own color_map, the algorithm ends up creating its
own two_bit_color_map.

I am using the following code:

template<class TGraph, class TVisitor>
int myDijkstra(TGraph& graph, TVisitor& visitor, int source)
        bool earlyExit = false;
        const int nVertices =boost::num_vertices(graph);
        std::vector<double> distances(nVertices);
        std::vector<typename TGraph::vertex_descriptor>
        std::vector<boost::default_color_type> colors(nVertices);

        try {
            boost::dijkstra_shortest_paths<TSubGraph, TVisitor >(
                graph, source,
                boost::predecessor_map( &predecessors[0] )
                .distance_map( &distances[0] )
                .visitor( visitor )
                .color_map( &colors[0] )
        } catch( EarlyExitByVisitor ) {
            earlyExit = true;
        return earlyExit ? CountBlackVertices(colors) : nVertices;

The code compiles and runs, but the vector of colors is never modified
(I can initialize it with different colors, makes no difference).
The predecessor and distance maps are fine.

Tracing what happens in the source code (boost version 1.43). I notice
that the Named Parameter Variant (line 466) gets the distance, weight
and index from the named parameter object. It then passes on to the
dijkstra_dispatch1 (line 443) that adds the default for the distance
map. It passes on to dijkstra_dispatch2 (line 413) that sets even more
parameters, but not the color map. Finally it calls
dijkstra_shortest_paths variant with default color_map (line 342), which
ignores the named parameter object and provides its own color map. (all
of the line numbers are in file dijkstra_shortest_paths.hpp).

My question is: is this a bug? Can I use named parameters if I want to
provide my own color_map? How?

Any help is appreciated.

Alex Hagen-Zanker

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