找到BGL图中路径中使用的平行边？-Java 学习之路

任何人都可以通过一个工作示例来显示如何确定在类型图形上从 astar_search() 获得的路径所使用的实际边缘： parallel edges （当相同的相邻源和目标顶点之间存在多条路径时）可能存在（与"costs"不同？

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

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

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

我应该说我并不完全熟悉boost库 - 我在C上也不是那么强大（C：是的，C：gulp！）BGL类型解析事物并自动提供一些数据结构的方式可能确实如此最大限度地利用它的灵活性 - 但对于缺乏经验的人（例如我）来说，确定特定用途IMVHO所使用或需要的实际元素类型有点令人困惑 .

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

回复于 2024-05-06T00:45:46+08:00

找到BGL图中路径中使用的平行边？

1 回答

相关问题