[Boost-users] [BGL] dijkstra_shortest_paths on dynamically growing and shrinking graphs

Subject: [Boost-users] [BGL] dijkstra_shortest_paths on dynamically growing and shrinking graphs
From: Ingo Maindorfer (ingo_at_[hidden])
Date: 2009-05-24 10:22:55

Hello,

consider the follwoing Graph:

struct EP {
       double weight;
};
typedef boost::adjacency_list< boost::listS, boost::vecS, 
boost::directedS, boost::no_property, EP > Graph;

The call of dijkstra_shortest_paths is clear to me on that graph:

boost::dijkstra_shortest_paths( m_graph,
       a_start_idx,
       weight_map( m_weight_map ).distance_map( 
&distance_vector[0]).predecessor_map( &parent_vector[0] ) );
       where parent_vector and distance_vector are plain std::vector of 
the according size.

Over time, I have to remove the "oldest" edges and vertices with lower 
index via remove_vertex() and remove_edge() from the graph and
add some "newer" edges and vertices to the graph.

My problem is, that the dijkstra_shortest_paths method dosen't work when 
I provide a plain std::vector to the distance_map() and predecessor_map()
parameter of the dijkstra_shortest_paths call because of the mapping 
from the vertex descriptor to position in the vector.

Can anybody tell me how to provide the "right" type of parameter for 
distance_map() and predecessor_map() ?

Maybe something like

boost::property_map< Graph, double EP::*>::type m_weight_map = 
boost::get( &EP::weight, graph );

that I'm already have done for the weight_map parameter but I'm looking 
for something that can handle the mapping stuff of vertex descriptors 
correctly.

Performance is not a subject because of a few hundred vertices and 
edges. I'm on Boost 1.39.

Kindly,

Ingo