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: Roger Leigh (rleigh_at_[hidden])
Date: 2016-01-13 18:00:22

On 13/01/2016 13:40, alex wrote:
>
>
>> 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've gone with (2) for now, and this appears to be working absolutely 
fine.  It's certainly giving the same results as the manually computed 
tables currently in use, which is good!

One thing I'm not totally sure about is how to get an edge list from 
dijkstra_shortest_paths.

   Graph g; // pre-filled
   vertex_descriptor start // set elsewhere

   std::vector<vertex_descriptor> predecessor(boost::num_vertices(g));
   std::vector<int64_t> distances(boost::num_vertices(g));

   boost::dijkstra_shortest_paths(g, start, 
boost::weight_map(boost::get(&Transform::weight, g)).
   distance_map(boost::make_iterator_property_map(distances.begin(), 
get(boost::vertex_index, g))).
  predecessor_map(boost::make_iterator_property_map(predecessor.begin(), 
boost::get(boost::vertex_index, g))));

Can I also append .edge_map() here to get a map of edges?  I want to be 
able to access the edge linking each vertex v to its parent 
predecessor[v], so I can use the bundled properties.  Or do I need to 
find it by hand / use some other Boost.Graph functionality I'm unaware of?

Thanks, very much for your advice.  I'm about 95% done now; it's just a 
matter of the last small detail to get it all working!

Kind regards,
Roger