построение графа библиотеки графов повышения; итеративное добавление свойств края

Я пытаюсь определить график, используя библиотеку графов повышения. Я прочитал из текстового файла, чтобы получить матрицу from_to_and_distance, как определено ниже. Я планировал просто перебрать матрицу, чтобы определить ребра графа, но не могу понять, как определить свойства ребер с помощью этого метода. В частности, я хотел бы использовать переменную Distance_from_a_to_b, как определено ниже, и назначать ее каждому краю объекта. Я относительно новичок в С++, как вы можете видеть, поэтому, хотя в документах библиотеки может быть ответ, я не могу его понять. Может кто-нибудь помочь? Я планирую передать этот график в алгоритм Дейкстры после его завершения — если это будет иметь значение.

Заранее спасибо!

struct site_properties{
};

struct reach_properties{
    double distance;
};

//Note that from_to_and_distance_matrix is std::vector<std::vector<double> > and
//includes inner vectors of [from_node,to_node,distance] 

boost::adjacency_list<boost::vecS,boost::vecS,boost::directedS,site_properties,reach_properties> graph(unique_node_ids.size());

for(unsigned int i = 0; i < from_to_and_distance_matrix.size(); i++){
    int node_a = (int)from_to_and_distance_matrix[i][0];
    int node_b = (int)from_to_and_distance_matrix[i][1];

    //How do I assign the distance_from_a_to_b variable to the edge?!
    double distance_from_a_to_b = from_to_and_distance_matrix[i][2];

    boost::add_edge(node_a,node_b,graph);
}

c++ boost graph boost-graph
person gcolumbus    schedule 04.12.2013    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Поскольку вы собираетесь передать его dijkstra (я полагаю, dijkstra_shortest_paths), вы можете упростить его, сохранив свои расстояния в свойстве edge_weight, которое этот алгоритм будет читать по умолчанию.

#include <vector>
#include <stack>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

int main()
{
    // [from_node,to_node,distance] 
    std::vector<std::vector<double>> from_to_and_distance_matrix =
        {{0,1,0.13}, {1,2,0.1}, {1,3,0.2},
         {2,3,0.1}, {1,3,0.3}, {2,4,0.1}};

    using namespace boost;
    typedef adjacency_list<listS, vecS, directedS, no_property,
                           property<edge_weight_t, double>> graph_t;
    graph_t g;
    for(auto& v: from_to_and_distance_matrix)
        get(edge_weight, g)[add_edge(v[0], v[1], g).first] = v[2];

    std::cout << "Loaded graph with " << num_vertices(g) << " nodes\n";

    // call Dijkstra
    typedef graph_traits<graph_t>::vertex_descriptor vertex_descriptor;
    std::vector<vertex_descriptor> p(num_vertices(g)); // predecessors
    std::vector<double> d(num_vertices(g)); // distances
    vertex_descriptor start = vertex(0, g); // starting point
    vertex_descriptor goal = vertex(4, g); // end point

    dijkstra_shortest_paths(g, start,
                            predecessor_map(&p[0]).distance_map(&d[0]));

    // print the results
    std::stack<vertex_descriptor> path;
    for(vertex_descriptor v = goal; v != start; v = p[v])
        path.push(v);
    path.push(start);

    std::cout << "Total length of the shortest path: " << d[4] << '\n'
              << "The number of steps: " << path.size() << '\n';
    while(!path.empty()) {
        int pos = path.top();
        std::cout << '[' << pos << "] ";
        path.pop();
    }
    std::cout << '\n';
}

онлайн-демонстрация: http://coliru.stacked-crooked.com/a/4f065507bb5bef35

person Cubbi    schedule 04.12.2013
comment
+1. Еще одна альтернатива, которая продолжает использовать связанные свойства на основе кода в этом ответе. - person llonesmiz; 04.12.2013