Re: [Boost-users] [graph] Search algorithm using quality metric rather than distance

Subject: Re: [Boost-users] [graph] Search algorithm using quality metric rather than distance
From: alex (alexhighviz_at_[hidden])
Date: 2016-01-13 08:40:19

>From: rleigh_at_[hidden]
>Sent: 13 January 2016 11:54

>Similar to the dijkstra_shortest_paths algorithm, I'd like to determine
>the optimal path. However, this algorithm sums the distance along each
>edge, and finds the shortest path. What I'd like to do is *multiply* the
>quality metric for each edge in the path, and find the largest one. A
>perfect path will have a quality metric of 1.0, while suboptimal paths
>will have values tending towards zero, and the more "bad" edges the
>smaller the number.
>

I think you can use dijkstra_shortest_paths and have two options to do so: 

1 .You can provide the Dijkstra algorithm with the appropriate
CombineFunction, CompareFunction, DistZero and DistInf (CombineFunction =
std::multiplies, CompareFunction  = std::greater, DistZero = 1, DistInf =
0;)

2. You can log-transform the quality metrics, using w = -log(q), where w is
the transformed weight for the WeightMap
 
>I'll likely then look at the number of edges and then select the shortest
>of the candidates.

Dijkstra will not give you multiple candidates, but just one highest-quality
path. 

If you want a more complex distance that considers both the number of edges
in path and their quality, you might be best of with a
std::tuple<QualityType, EdgeCountType> for Distance and provide the Dijkstra
algorithm with the appropriate CombineFunction, CompareFunction, DistZero
and DistInf.

>
>It seems like a simple algorithm that might already be included, but I
>just haven't found it yet not knowing its formal name. If anyone has any
>suggestions, I'd be very grateful.
>
>
>Many thanks,
>Roger