在BGL图形的路径中寻找哪条平行边缘被使用？
任何人都可以显示，用工作实施例，如何人们可能确定通过从所获得的路径中使用的实际边缘astar_search()上式的曲线图： adjacency_list<multisetS,vecS,directedS,location,route>当平行边缘 （之间的多个路由相同的相邻源和目标顶点）可能存在（具有不同的“成本”）？
location和route是我作为顶点和边缘的捆绑属性的自定义结构。
我本来打算使用listS （特别是std :: list）作为outEdgesList的类型，但我明白如果我想用out_edge_range(source, target, graph)来检索连接源和目标的所有边，它需要是一个multisetS （一个允许重复值的“有序集合”） - 在最坏的情况下，我将不得不退回到从目的地到起点的找到路径的顶点，并使用当前和之前的顶点回想起所有可能的边缘，然后选择最低的“成本” - 但如果搜索已经完成了寻找路径，那么这似乎有点不理想。
我被引导认为edge_predecessor_recorder访问者可能是记下所选特定边的一种方式，但我一直无法找到一个代码示例来显示它正在使用中 - 该特定访问者是否可以用在A的前驱地图上*搜索？
我应该说，我并不完全熟悉boost库 - 而且我对C ++没有那么强大（C：是，C ++：gulp！）BGL typedef事物并自动提供某些数据结构的方式可能的确的确如此，最大限度地利用它的灵活性 - 但是对于没有经验的人（例如我）来说，为了特定使用IMVHO而使用或需要的实际类型的元素是有点混淆的。
我认为你在正确的轨道上。 这对我有效：
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;
}
}
上一篇: Finding which parallel edge was used in a path in a BGL graph?