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: The Maschine (justthemaschine_at_[hidden])
Date: 2013-04-16 10:59:46

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?

Thanks a lot,
Tasos

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