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 11:01:33

On Tue, 16 Apr 2013, The Maschine wrote:

> Hi Jeremiah,
> 
> As far as I understand this will examine only the "local" value (node 
> length for example) against the threshold.
> 
> In my path search I need to be able to find the "total length/distance" 
> from the source to the vertex in question. Adding up the lengths (of the 
> nodes that the path is passing) from source to current vertex and then 
> tested against the threshold.
> 
> Am I clear or my description is wrong?

I had assumed you were using m_length as the distance map in Dijkstra's 
algorithm, and so that would be the total distance you want to compare to. 
Is that what you intended?  If not, what are you using as your distance 
map?

-- Jeremiah Willcock

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