On 13/01/2016 13:40, alex wrote:
From: rleigh@codelibre.net 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