algorithm - 查找在 BGL 图中的路径中使用了哪条平行边？

Question

任何人都可以用一个工作示例来说明如何确定从 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* 搜索的前身 map 上使用？

我应该说我并不完全熟悉 boost 库——而且我对 C++ 也不是很了解(C:是的，C++:gulp!)BGL 类型定义的方式并自动提供一些数据结构确实可以最大化利用它的灵 active ——但对于没有经验的人(例如我)来说，确定特定用途 IMVHO 使用或需要的元素的实际类型有点令人困惑。

Answer 1

我认为您走在正确的轨道上。这对我有用:

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;
    }
}