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 12:43:55

On Tue, 16 Apr 2013, The Maschine wrote:

> Hi,
> 
> Not really! (Im not that advance yet) Let me explain.
> 
> 1) Every vertex in the graph has each own m_length value which is the 'length' of that node only.

In the sense of doing navigation on terrain or that sort of thing?  I.e., 
do you intend that nodes have a cost to travel through (into or out of)?

> 2) from the "source" of the search, I want the search to extent to only 
> the node in the radius from the source. So that "radius" cutoff should 
> by something like adding all "m_length" of the route to the current 
> node.

OK.  The distance map in the algorithm represents the sum of all edge 
weights in the best path to each vertex, so that is what you would want to 
compare to your threshold.

> At the moment my search only has a weight_map of the "Edge Weights" not 
> some sort of "Vertex Weight".

Didn't you say above that you want to use vertex weights?  If so, you will 
need to translate those to edge weights (by applying the weight of each 
vertex to its neighboring edges); for an undirected graph, an edge's 
weight will likely be the average of the weights of its endpoints.

> How should I proceed? Is this clear? Sorry for the confusion.

What do you want to get as the result of your computation?

-- Jeremiah Willcock