Boost logo

Boost Users :

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


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net