[graph] Search algorithm using quality metric rather than distance
I have an adjacency_list graph (shown in attached dot file). Each edge has an attached "quality metric" as a bundled property. 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'll likely then look at the number of edges and then select the shortest of the candidates. 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
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'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
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
From: Roger Leigh Can I also append .edge_map() here to get a map of edges?
No
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?
You can use the boost::edge(u,v,graph) function. auto edge_descriptor = boost::edge(predecessor[v], v, g).first;
hello, I have a modeling question for seasoned boost graph practitioners: I am modelling a dataflow DAG where nodes have input and output ports and edges can connect output ports to input ports. I am already using a temporary boost::graph during the compilation process to detect feedback loops, compute the topological sort and parallel ordering...etc For that task it is enough to forget about the notion of ports and only have one vertex per node and edges between nodes. However I would like to avoid rebuilding the graph each time a node or connection is added and use boost::graph as my primary model. A simple solution I have found is to annotate edges with some edge properties to keep track of the source and target ports in the respective nodes. However that solution has some shortcomings: it is not possible to use out_degree, in_degree, out_edges, in_edges...etc for a specific port, one has to manually scan all the edges and select the ones matching the port of interrest. As an alternative, I have thought about building a bigger graph with one vertex for each node and each port and subgraphs to group nodes with their input / output ports. However in this case it is no longer easy to get all the out_edges for a node, one has to aggregate all the out_edges of each output port. I suppose this is a common modeling problem. I would be happy to hear about other solutions to this problem and their potential advantages and drawbacks. best regards.
participants (6)
-
a.hagen-zanker＠surrey.ac.uk -
alex -
Remy Muller -
rleigh＠codelibre.net -
Roger Leigh