Re: [Boost-users] [graph] dijkstra additional constrains that will stop the search (ex. distance from source)

Subject: Re: [Boost-users] [graph] dijkstra additional constrains that will stop the search (ex. distance from source)
From: a.hagen-zanker_at_[hidden]
Date: 2013-04-17 10:57:25

From: Boost-users [mailto:boost-users-bounces_at_[hidden]] On Behalf Of The Maschine

boost::dijkstra_shortest_paths(m_ugraph, *vertex_iterator_begin, boost::predecessor_map(predecessorMap).distance_map(distanceMap));
currently works ok. 
Finds the shortest path based on the "edge_weight" (this is what I need).

The addition I need: I need the search for the shortest path to stop if outside a radius. (my graph is a street network).

lets say max "travel distance" = 4 
Source -> V1(length=1) -> V2(length=3) -> V3(length=2) -> V4(length=1) -> V5(length=1) ->VEnd

The search should end on V3 and V3 should be "unreachable" from the source (V4,V5 and Vend should be unreachable too)

The distance_map should have the distances for V1 and V2 based on the "edge_weight".

This explanation seems to be better.

Thanks
Tasos

Hi Tasos,

You could consider that "unreachable" is the same as "d = travel distance". You could use a closed plus and a custom value for infinite distance. You would need to create a closed plus that is a bit more robust than the closed_plus currently in BGL, e.g.:

struct robust_closed_plus {
  robust_closed_plus (double d) : d(d)
  {}

  double operator(double a, double b){
    return (d-a < b) >? d : a+b;
  }
  double d;
};

Then you can use dijkstra_shortest_path, using your travel distance as infinity. 

robust_closed_plus plusser(travel_distance); 

boost::dijkstra_shortest_paths(m_ugraph, *vertex_iterator_begin
  , boost::predecessor_map(predecessorMap)
  .distance_map(distanceMap)
  .distance_compare(plusser)
  .distane_inf(travel_distance);

This should already give you the correct result, but will also make you visit more vertices than necessary. Still combine with a visitor like Jeremiah suggested before:

struct hit_inf{};

template<typename DistanceMap>
struct inf_quit_visitor: boost::default_dijkstra_visitor {
  inf_quit_visitor (DistanceMap dm, double inf) : dm(dm), inf(inf)
  {}

  template<typename V, typename G>   
  void examine_vertex(V v, const G& g) {
     if (get(dm, v) == inf)
       throw hit_inf();
   }

  DistanceMap dm;
  double inf;
};

robust_closed_plus plusser(travel_distance);

inf_quit_visitor<DistanceMap> quitter(distanceMap, travel_distance);

try
{
  boost::dijkstra_shortest_paths(m_ugraph, *vertex_iterator_begin, 
    boost::predecessor_map(predecessorMap)
    .distance_map(distanceMap)
    .distance_compare(plusser)
    .distane_inf(travel_distance)
    .visitor(quitter) );
} catch(hit_inf&) {
}

Hope this helps, Alex