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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-04-16 10:37:59

On Tue, 16 Apr 2013, The Maschine wrote:

> Hi all,
>
> I've been reading around the list (Ill post examples below) but I dont
> really know how to implement the thing below.
>
> I want the search to be able to stop based on some "value" or "result
> of a function". For example, every node has a "length" value in a
> custom "struct VertexProperties".
>
> How is it possible for dijkstra_shortest_paths to only consider nodes
> that are inside a radius from the source? Everything else should be
> considered as 'unconnected'.
>
> I have checked a couple of posts form the list but I dont know what do
> really do. (function property map, exceptions in visitors etc)
> http://thread.gmane.org/gmane.comp.lib.boost.user/54392/focus=54397
> http://thread.gmane.org/gmane.comp.lib.boost.user/72072/focus=72074
> http://thread.gmane.org/gmane.comp.lib.boost.user/73358/focus=73384
>
> I havent found any example or source online that deals with something similar.
>
> Any ideas? code example or tutorials?
>
> Best,
> Tasos
>
> my graph for example:
> struct VertexProperties
> {
>    double m_length;
>    int m_ref;
> };
>
> typedef double Weight;
> typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty;
> typedef boost::adjacency_list<boost::vecS, boost::vecS,
> boost::undirectedS, VertexProperties, EdgeWeightProperty> unGraph;

Here's the basic idea (not tested); use this as your Dijkstra visitor, and 
change the part labeled "threshold" to your threshold computation:

struct threshold_visitor: boost::default_dijkstra_visitor {
   double threshold;

   threshold_visitor(double threshold): threshold(threshold) {}

   struct hit_threshold {};

   void examine_vertex(vertex_descriptor v, const unGraph& g) {
     if (get(&VertexProperties::m_ref, g, v) > threshold)
       throw hit_threshold();
   }
};

Remember to wrap your call to Dijkstra's algorithm in a try-catch block 
for threshold_visitor::hit_threshold.

-- Jeremiah Willcock