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-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
{
public:
    typedef typename TGraph::vertex_descriptor TVertex;
    typedef typename TGraph::edge_property_type::value_type TEdge; // 
EDGE PROPERTY, NOT DESCRIPTOR

    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>;
    }

    ~ResumableDijkstra()
    {
        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;

        m_Colors->assign(nVertices, 
boost::color_traits<boost::default_color_type>::white());

        m_Predecessors->resize(nVertices);
        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;

        ModifyGraph(restoreEdges);
       
        try {
            boost::dijkstra_shortest_paths_no_init<TGraph, TVis>(
                *m_Graph,
                m_Origin,
                &((*m_Predecessors)[0]),
                &((*m_Distances)[0]),
                boost::get(&TEdge::m_Cost, *m_Graph), 
                boost::get(boost::vertex_index, *m_Graph),
                std::less<double>(),
                boost::closed_plus<double>(),
               (double) 0.0,
                visitor,
                &((*m_Colors)[0])
            );
        } catch(AxExit) {
            finished =  false;
        }

        RestoreGraph(restoreEdges);

        if(!finished) {
            ListGrayVertices();
        }

        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], 
*m_Graph);
                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;
            }
        }
        m_GrayVertices->clear();
        m_GrayVertexDistances->clear();

        restoreEdges.clear();
    }

    void ListGrayVertices()
    {
        m_GrayVertices->clear();
        m_GrayVertexDistances->clear();
        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_GrayVertices->push_back(j);
                m_GrayVertexDistances->push_back((*m_Distances)[j] );
               
                (*m_Distances)[j] = std::numeric_limits<double>::max();
                (*m_Predecessors)[j] = j;
                (*m_Colors)[j] = 
boost::color_traits<boost::default_color_type>::white();
            }
        }
    }

    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;
};