BGL - пользовательский посетитель, который взвешивает веса ребер по предыдущему шагу - PullRequest
Новая
       22

BGL - пользовательский посетитель, который взвешивает веса ребер по предыдущему шагу

0 голосов
/ 06 февраля 2019

У меня есть ориентированный граф, который, как я знаю, не имеет циклических зависимостей и имеет «конечные» узлы, то есть у них есть собственное свойство вершины, которое я могу проверить.Каждое ребро взвешивается с использованием встроенного свойства веса ребра BGL.

Что я хочу сделать, это пройтись от любой вершины по всем возможным путям, пока она не достигнет всех узлов завершения, которые могут быть достигнуты, и отследить "weighted "граничные веса каждого конечного узла достигнутыПод этим я подразумеваю, что следующее лучше всего объяснить следующим простым примером.

Скажем, из узла 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, я полагаю, мне нужен какой-то пользовательский посетитель / предшественник?

Любая помощь очень ценится.

1 Ответ

0 голосов
/ 06 февраля 2019

Ваш пример расчетов довольно запутанный.Я предполагаю, что вы имели в виду делать то, что говорит ваше описание: "сумма взвешенных весов ребер, которые шли на пути к каждому узлу" , поэтому: 

{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}, }
...