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

Question

任何人都可以通过一个工作示例来说明如何确定从 astar_search() 类型的图上获得的路径所使用的实际边：adjacency_list<multisetS,vecS,directedS,location,route> when parallel edges（同一相邻源和目标顶点之间的多条路线）可能存在（具有不同的"costs"）？

location 和 route 是自定义结构，我将其作为顶点和边的捆绑属性。

我原本打算使用 listS（特别是 std::list）作为 outEdgesList 的类型，但我知道如果我想使用 out_edge_range(source, target, graph) 来检索所有连接源和目标的边，它需要是一个 multisetS（一个允许重复值的 "ordered set"？）——在最坏的情况下，我将不得不通过从目的地到找到的路径的顶点退后一步开始，并使用当前和先前的顶点来召回所有可能涉及的边，然后选择具有最低 "cost" 的边 - 但如果搜索已经完成，那么这似乎有点非最佳路径...!

我被引导相信 edge_predecessor_recorder 访问者可能是一种记下所选特定边缘的方法，但我无法找到代码示例显示它在使用中 - 该特定访问者甚至可以 在 A* 搜索的前任地图上使用 吗？

我应该说我对 boost 库不是很熟悉——而且我对 C++ 也不是很了解（C：是的，C++：gulp !) BGL typedef 自动提供一些数据结构的方式确实可以最大化使用它的灵活性 - 但是对于没有经验的人（例如我）来说，确定所使用的实际元素类型有点混乱或特定用途所需的 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;
    }
}

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

Finding which parallel edge was used in a path in a BGL graph?

algorithm

a-star

boost-graph