c++ - BGL - 通过上一步加权边缘权重的自定义访问者

Question

我有一个有向图，我知道它没有任何循环依赖关系并且有“终止”节点，即它们有一个自定义顶点属性，这是一个我可以检查的布尔值。使用 BGL 内置的边权重属性对每条边进行加权。

我想要做的是沿着所有可能的路径从任何顶点步行，直到它到达所有可以到达的终止节点并跟踪到达的每个终止节点的“加权”边权重。我的意思是，下面的简单示例可以最好地解释以下内容。

假设从节点 4 开始，有以下带有权重的边，如果 T（终止）

4->1 : 0.25 : T
4->5 : 0.45
4->6 : 0.5
5->2 : 0.65 : T
6->3 : 0.18 
6->7 : 0.44 : T
3->1 : 0.33 : T

我想返回一个对的向量，它是在到达每个节点的途中经过的终止节点/边缘权重的“加权”组合，在这种情况下将是：

{1, 0.25 + (0.5*0.18*0.33) }
{2, (0.45*0.65)}
{7, (0.5*0.44)}
Final Result : [ {1, 0.2797}, {2, 0.2925}, {7, 0.22}]

通过“加权”，我的意思是每个新步骤都由在特定路径上行走的所有先前边缘权重的乘积加权。

所以从 4 到终止节点 1，有两条路径。直接边缘为 1，权重为 0.25。还有一条路径是 4->6->3->1，即 0.5*0.18*0.33。因此，对于节点 1，我们的总权重为 0.25 + (0.5*0.18*0.33) = 0.2797。

再次从 4 到终止节点 2，有一条到 4->5->2 (0.45*0.65) 的路径，所以节点 2 = 0.2925

最后 4 到终止节点 7，路径 4->6->7，(0.5*0.44)，所以节点 7 = 0.22

这在 BGL 中是否可行，我想我需要某种自定义访问者/前任？

非常感谢任何帮助。

标签： c++boostgraphboost-graph

Answer 1

您的示例计算非常混乱。我假设您打算按照您的描述进行操作：“在到达每个节点的途中经过的加权边缘权重的总和”，因此：

{1, 0.25}
{2, (0.45+0.65)}
{7, (0.5+0.44)}
Final Result : [ {1, 0.25}, {2, 1.1}, {7, 0.94}]

这是一个最短路径问题。如果您例如使用dijkstra_shortest_paths您正在寻找的结果将在distance_map. 只需从该地图中选择“终止顶点”即可完成：

Live On Coliru

//#include <boost/spirit/home/x3.hpp>
#include <boost/graph/adjacency_list.hpp>

using Weight = double;
struct EdgeProps { Weight weight = 0; };

using Graph = boost::adjacency_list<
    boost::vecS, boost::vecS, boost::directedS, boost::no_property, EdgeProps>;

Graph make_sample();

#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>

int main() {

    auto const g     = make_sample();
    auto const start = vertex(4, g);

    print_graph(g);

    // property-maps maps for dijkstra:
    auto constexpr INF = std::numeric_limits<Weight>::infinity();
    std::vector<Graph::vertex_descriptor> pred(num_vertices(g));
    std::vector<Weight> dist(num_vertices(g), INF);

    dijkstra_shortest_paths(g, start, boost::predecessor_map(pred.data())
            .distance_map(dist.data())
            .weight_map(get(&EdgeProps::weight, g))
            .distance_inf(INF));

    // print results
    std::cout << "Final Result : [ ";

    for (auto vd : boost::make_iterator_range(vertices(g))) {
        if (INF != dist[vd] && 0 == out_degree(vd, g)) {         // if reachable and leaf,
            std::cout << "{" << vd << ", " << dist[vd] << "}, "; // print total distance from start
        }
    }

    std::cout << "}\n";
}

Graph make_sample() {
    Graph g(8);
    add_edge(4, 1, EdgeProps{0.25}, g); // : T
    add_edge(4, 5, EdgeProps{0.45}, g);
    add_edge(4, 6, EdgeProps{0.5},  g);
    add_edge(5, 2, EdgeProps{0.65}, g); // : T
    add_edge(6, 3, EdgeProps{0.18}, g);
    add_edge(6, 7, EdgeProps{0.44}, g); // : T
    add_edge(3, 1, EdgeProps{0.33}, g); // : T
    return g;
}

印刷

0 --> 
1 --> 
2 --> 
3 --> 1 
4 --> 1 5 6 
5 --> 2 
6 --> 3 7 
7 --> 
Final Result : [ {1, 0.25}, {2, 1.1}, {7, 0.94}, }