Finding which parallel edge was used in a path in a BGL graph?
Can anyone show, with a working example, how one might determine the actual edges used by path obtained from an astar_search() on a graph of type: adjacency_list<multisetS,vecS,directedS,location,route> when parallel edges (multiple routes between the same adjacent source and target vertex) are likely to be present (with different "costs")?
location and route are custom structures that I have as bundled properties for vertices and edges.
I originally was going to use a listS (specifically a std::list) as the type for the outEdgesList but I understand that if I wanted to use out_edge_range(source, target, graph) to retrieve all the edges linking source and target, it needs to be a multisetS (an "ordered set" which permits duplicate values?) - in the worst case I would have to step back through the vertexes of the found path from destination to start, and use the current and previous vertexes with that to recall all the possible edges involved and then pick the one with the lowest "cost" - but that seems a bit non-optimal if the search has already done just that to find the path...!
I am led to believe an edge_predecessor_recorder visitor might be a way to note down the particular edge selected but I have not been able to find a code sample that shows it in use - can that particular visitor even be used on the predecessor map from an A* search?
I should say that I am not totally familiar with the boost libraries - and I'm not that strong on C++ (C: yes, C++: gulp !) The way that the BGL typedefs things and provides some data structures automagically may, indeed, maximise the flexibility to utilise it - but it is a little confusing for the inexperienced (me, for example) to pin down the actual types of elements used or needed for a particular use IMVHO.
I think you're on the right track. This worked for me:
struct location_t { // vertex properties
std::string name;
};
struct route_t { // edge properties
std::size_t distance;
};
typedef adjacency_list<listS,vecS,directedS,location_t,route_t> graph_t;
typedef graph_traits<graph_t>::edge_descriptor edge_t;
typedef graph_traits<graph_t>::vertex_descriptor vertex_t;
struct heuristic {
heuristic(vertex_t dest) : dest_(dest) {}
std::size_t operator()(vertex_t src) {
// only needs to be "optimistic", so:
return (src == dest_) ? 0 : 1 ;
}
private:
vertex_t dest_;
};
typedef std::map<vertex_t, edge_t> pred_edge_map_t;
typedef associative_property_map<pred_edge_map_t> pred_edge_pmap_t;
int main() {
graph_t g;
// insert four vertices and a mix of singular and parallel edges
vertex_t zero = add_vertex(location_t{"A"}, g); // source
vertex_t one = add_vertex(location_t{"B"}, g);
vertex_t two = add_vertex(location_t{"C"}, g);
vertex_t three = add_vertex(location_t{"D"}, g); // sink
// optimal path: 0->2->3 (cost 6)
add_edge(zero, one, route_t{3}, g);
add_edge(zero, one, route_t{5}, g); // parallel to previous edge
add_edge(zero, two, route_t{4}, g);
add_edge(one, three, route_t{4}, g);
add_edge(two, three, route_t{2}, g);
add_edge(two, three, route_t{4}, g); // parallel to previous edge
// construct predecessor map
pred_edge_map_t pred;
pred_edge_pmap_t pred_pmap(pred);
// construct visitor that uses it
auto recorder = record_edge_predecessors(pred_pmap, on_edge_relaxed());
astar_visitor<decltype(recorder)> visitor(recorder);
astar_search(g, zero, heuristic(three),
weight_map(get(&route_t::distance, g)).
visitor(visitor));
// extract route (in reverse order)
for (vertex_t v = three; v != zero; v = source(pred_pmap[v], g)) {
auto e = pred_pmap[v];
std::cout << g[source(e, g)].name << "->" << g[target(e, g)].name << " with weight " << g[pred_pmap[v]].distance << std::endl;
}
}