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-06 08:06:33

The problem of resuming a dijkstra_shortest_path calculation is solved
and I thought to share the solution here.

It works now without making a copy of the input graph and without
permanently modifying the graph as I wrote earlier.

The color map is used to make a list of gray vertices (i.e. those
vertices in the queue). Before resuming using
dijkstra_shortest_path_no_init edges are inserted that connect the
source to the gray vertices (i.e. they will be lined up to be put in the
queue again). The distance of these edges is the same as the vertex
distance of the gray vertices. Subsequently the gray vertices are
colored white (i.e. marked as if not in the queue yet).

The effect of these actions is that the gray vertices will be inserted
into the priority queue by the breadth_first_visit() at their
appropriate distance.

After the dijkstra_shortest_path_no_init, it is necessary to clean up
the introduced edges. There is some overhead to deal with the case that
there are already edges between the gray vertices and the origin. Also
there is some overhead to make sure that tentative distances and
predecessors are not retained, but that is not essential.

My code is below, it is not as generic as the BGL though.

Jeremiah, Thanks for your help!

template<class TGraph>
class ResumableDijkstra
    typedef typename TGraph::vertex_descriptor TVertex;
    typedef typename TGraph::edge_property_type::value_type TEdge; //

    ResumableDijkstra() : m_Graph(NULL), m_Predecessors(NULL),
m_Distances(NULL), m_Colors(NULL), m_GrayVertexDistances(NULL)
        m_Predecessors = new std::vector<TVertex>;
        m_Distances = new std::vector<double>;
        m_Colors = new std::vector<boost::default_color_type>;
        m_GrayVertices = new std::vector<TVertex>;
        m_GrayVertexDistances = new std::vector<double>;

        delete m_Predecessors;
        delete m_Distances;
        delete m_Colors;
        delete m_GrayVertices;
        delete m_GrayVertexDistances;
    void Initialize(TGraph& graph, TVertex origin)
        m_Origin = origin;
        m_Graph = &graph;
        const int nVertices = boost::num_vertices(graph);
        m_Distances->assign(nVertices, std::numeric_limits<double>::max());
        (*m_Distances)[m_Origin] = 0;


        for(int i = 0; i < nVertices; i++) {
            (*m_Predecessors)[i] = (TVertex) i;

    template<class TVis>
    bool Expand(const TVis& visitor)
        bool finished = true;
        std::vector<TEdge*> restoreEdges;

        try {
            boost::dijkstra_shortest_paths_no_init<TGraph, TVis>(
                boost::get(&TEdge::m_Cost, *m_Graph),
                boost::get(boost::vertex_index, *m_Graph),
               (double) 0.0,
        } catch(AxExit) {
            finished = false;


        if(!finished) {

        return finished;

    void ModifyGraph(std::vector<TEdge*>& restoreEdges)
        const int n = m_GrayVertices->size();
        restoreEdges.assign(n, NULL);
        for(int i = 0; i < n; ++i) {
            if( boost::edge(m_Origin, (*m_GrayVertices)[i],
*m_Graph).second ) {
                TEdge* e = new TEdge;
                *e = (*m_Graph)[boost::edge(m_Origin,
(*m_GrayVertices)[i], *m_Graph).first];
                boost::remove_edge(m_Origin, (*m_GrayVertices)[i],
                restoreEdges[i] = e;
            TEdge edge;
            edge.m_Cost =(*m_GrayVertexDistances)[i];
            boost::add_edge(m_Origin, (*m_GrayVertices)[i], edge, *m_Graph);

    void RestoreGraph(std::vector<TEdge*>& restoreEdges)
        const int n = (int) m_GrayVertices->size();
        assert(n == (int)restoreEdges.size() );
        for(int i = 0; i < n; ++i) {
            boost::remove_edge(m_Origin, (*m_GrayVertices)[i], *m_Graph);
            if( restoreEdges[i] != NULL) {
                boost::add_edge(m_Origin, (*m_GrayVertices)[i],
*(restoreEdges[i]), *m_Graph);
                delete restoreEdges[i];
                restoreEdges[i] = NULL;


    void ListGrayVertices()
        const int nVertices = m_Colors->size();
        for(int j = 0; j < nVertices; j++) {
            if((*m_Colors)[j] ==
boost::color_traits<boost::default_color_type>::gray() && j != m_Origin) {
                m_GrayVertexDistances->push_back((*m_Distances)[j] );
                (*m_Distances)[j] = std::numeric_limits<double>::max();
                (*m_Predecessors)[j] = j;
                (*m_Colors)[j] =

    TGraph* m_Graph;

    std::vector<TVertex>* m_Predecessors;
    std::vector<double>* m_Distances;
    std::vector<boost::default_color_type>* m_Colors;

    std::vector<TVertex>* m_GrayVertices;
    std::vector<double>* m_GrayVertexDistances;
    TVertex m_Origin;

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