BGL получить карту весов для графа - PullRequest
Новая
       18

BGL получить карту весов для графа

0 голосов
/ 01 июня 2018

Я хотел бы реализовать взвешенный неориентированный граф с подграфами.Вот мой код инициализации для этого графа: 

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/subgraph.hpp>

typedef boost::property<boost::edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
                              boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>,
                              EdgeWeightProperty>
    UndirectedGraph;

typedef boost::subgraph<UndirectedGraph> UndirectedGraphS;

int main() {
    enum { A, B, C, D, E, F, num_vertices };

    // initialize our graph
    UndirectedGraphS graph(num_vertices);                     // add the edges
    UndirectedGraphS &coloredGraph = graph.create_subgraph(), // subgraph containing start nodes
        uncoloredGraph = graph.create_subgraph();             // main subgraph

    // fill the subgraph containing the start nodes
    std::vector<UndirectedGraphS::vertex_descriptor> coloredVertLabels = { A, E, F };

    auto addVerticesLabels = [](UndirectedGraphS &g, const std::vector<UndirectedGraphS::vertex_descriptor> &list) {
        for (const auto &l : list) {
            boost::add_vertex(l, g);
        }
    };

    addVerticesLabels(coloredGraph, coloredVertLabels);

    // fill the main subgraph
    typedef UndirectedGraphS::vertex_descriptor vertex_descriptor;
    //typedef boost::graph_traits<UndirectedGraphS>::edge_descriptor EdgeDesc;

    std::vector<vertex_descriptor> uncoloredVertLabels = { B, C, D };
    addVerticesLabels(uncoloredGraph, uncoloredVertLabels);
    // add the edges
    auto add_edge_wrap = [](const vertex_descriptor &v1, const vertex_descriptor &v2, int w, UndirectedGraphS &g) {
        boost::add_edge(v1, v2, static_cast<UndirectedGraphS::edge_property_type>(w), g);

    };

    // boost::get_property(graph, boost::graph_name) = "common";
    // boost::get_property(coloredGraph, boost::graph_name) = "colored";
    // boost::get_property(uncoloredGraph, boost::graph_name) = "uncolored";

    add_edge_wrap(A, B, 1, graph);
    add_edge_wrap(B, D, 3, graph);
    add_edge_wrap(D, E, 1, graph);
    add_edge_wrap(E, C, 7, graph);
    add_edge_wrap(C, A, 1, graph);
    add_edge_wrap(A, D, 2, graph);
    add_edge_wrap(C, D, 2, graph);
}

Теперь я хочу получить карту весов для алгоритма Дейкстры и попробовать использовать код: 

boost::property_map<UndirectedGraphS, int>::type weightmap = get(boost::edge_weight, graph);

Но возникает ошибка компилятора: 

In file included from /usr/include/boost/graph/adjacency_list.hpp:246:0,
                 from /home/galactic/CLionProjects/kandinsky/main.cpp:9:
/usr/include/boost/graph/detail/adjacency_list.hpp: In instantiation of ‘struct boost::vec_adj_list_any_vertex_pa::bind_<int, boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> >, boost::property<boost::vertex_index_t, int> >’:
/usr/include/boost/graph/detail/adjacency_list.hpp:2635:12:   required from ‘struct boost::detail::vec_adj_list_choose_vertex_pa<int, boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> >, boost::property<boost::vertex_index_t, int> >’
/usr/include/boost/graph/detail/adjacency_list.hpp:2761:12:   required from ‘struct boost::vec_adj_list_vertex_property_selector::bind_<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> >, boost::property<boost::vertex_index_t, int>, int>’
/usr/include/boost/graph/properties.hpp:201:12:   required from ‘struct boost::detail::vertex_property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> >, int>’
/usr/include/boost/graph/properties.hpp:212:10:   required from ‘struct boost::property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> >, int, void>’
/usr/include/boost/graph/subgraph.hpp:869:65:   required from ‘struct boost::detail::subgraph_global_pmap::bind_<int, boost::subgraph<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> > >, boost::property<boost::vertex_index_t, int> >’
/usr/include/boost/graph/subgraph.hpp:934:37:   required from ‘struct boost::detail::subgraph_choose_pmap<int, boost::subgraph<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> > >, boost::property<boost::vertex_index_t, int> >’
/usr/include/boost/graph/subgraph.hpp:944:43:   required from ‘struct boost::detail::subgraph_property_generator::bind_<boost::subgraph<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> > >, boost::property<boost::vertex_index_t, int>, int>’
/usr/include/boost/graph/properties.hpp:201:12:   required from ‘struct boost::detail::vertex_property_map<boost::subgraph<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> > >, int>’
/usr/include/boost/graph/properties.hpp:212:10:   required from ‘struct boost::property_map<boost::subgraph<boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::property<boost::vertex_index_t, int>, boost::property<boost::edge_index_t, int>, boost::property<boost::edge_weight_t, int> > >, int>’
/home/galactic/CLionProjects/kandinsky/main.cpp:315:47:   required from here
/usr/include/boost/graph/detail/adjacency_list.hpp:2584:29: error: forming reference to void
         typedef value_type& reference;
                             ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2585:35: error: forming reference to void
         typedef const value_type& const_reference;
                                   ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2588:55: error: forming reference to void
           <Graph, Graph*, value_type, reference, Tag> type;
                                                       ^
/usr/include/boost/graph/detail/adjacency_list.hpp:2590:67: error: forming reference to void
           <Graph, const Graph*, value_type, const_reference, Tag> const_type;
                                                                   ^

У меня есть предположение, что подграф работает неправильно со связанными свойствами, но использование внутреннего члена класса UndirectedGraphS типа UndirectedGraph приводит к той же ошибке.Скажите, пожалуйста, что не так с созданием шаблона

1 Ответ

0 голосов
/ 01 июня 2018

Ваш typedef 

typedef boost::property<boost::edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
                              boost::property<boost::vertex_index_t, int>,
                              boost::property<boost::edge_index_t, int>,
                              EdgeWeightProperty> UndirectedGraph;

определяет EdgeWeightProperty как свойство графика .Вместо этого вам нужны и индекс края, и вес: 

typedef boost::property<boost::edge_index_t, int, boost::property<boost::edge_weight_t, int> > EdgeProperty;

И используйте их оба для края: 

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
      boost::property<boost::vertex_index_t, int>,
      EdgeProperty> UndirectedGraph;

Теперь вы можете просто boost::get(boost::edge_weight, g), например: 

boost::property_map<UndirectedGraphS, boost::edge_weight_t>::type 
    weightmap = boost::get(boost::edge_weight, graph);

Несколько других проблем: 

UndirectedGraphS &coloredGraph = graph.create_subgraph(), // subgraph containing start nodes
    uncoloredGraph = graph.create_subgraph();             // main subgraph

Это случайно создает бесполезную копию для uncoloredGraph: 

static_assert(std::is_reference<decltype(uncoloredGraph)>{}, "oops");

Предотвратите это, став более явным: 

UndirectedGraphS graph(num_vertices);           // add the edges
auto &coloredGraph   = graph.create_subgraph(); // subgraph containing start nodes
auto &uncoloredGraph = graph.create_subgraph(); // main subgraph

Множество вещей может (и должно) быть проще: 

enum { A, B, C, D, E, F, num_vertices };

Sub graph(num_vertices);           // add the edges
auto &coloredGraph   = graph.create_subgraph(); // subgraph containing start nodes
auto &uncoloredGraph = graph.create_subgraph(); // main subgraph

for (auto l : {A, E, F}) boost::add_vertex(l, coloredGraph); 
for (auto l : {B, C, D}) boost::add_vertex(l, uncoloredGraph); 

add_edge(A, B, EdgeProps{ 1, 1 }, graph);
add_edge(B, D, EdgeProps{ 2, 3 }, graph);
add_edge(D, E, EdgeProps{ 3, 1 }, graph);
add_edge(E, C, EdgeProps{ 4, 7 }, graph);
add_edge(C, A, EdgeProps{ 5, 1 }, graph);
add_edge(A, D, EdgeProps{ 6, 2 }, graph);
add_edge(C, D, EdgeProps{ 7, 2 }, graph);

Добавление карт имен, печать графиков

Просто для ощущения того, как графики заканчиваются:

Live On Coliru 

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/subgraph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/property_map/function_property_map.hpp>

typedef boost::property<boost::edge_weight_t, int,
        boost::property<boost::edge_index_t, int> > EdgeProps;

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
                              boost::property<boost::vertex_index_t, int>, 
                              EdgeProps> Graph;

typedef boost::subgraph<Graph> Sub;
typedef Sub::vertex_descriptor Vertex;

int main() {
    enum { A, B, C, D, E, F, num_vertices };
    char const* names[num_vertices] = { "A", "B", "C", "D", "E", "F" };

    // initialize our graph
    Sub graph(num_vertices);           // add the edges
    auto &coloredGraph   = graph.create_subgraph(); // subgraph containing start nodes
    auto &uncoloredGraph = graph.create_subgraph(); // main subgraph

    for (auto l : {A, E, F}) boost::add_vertex(l, coloredGraph); 
    for (auto l : {B, C, D}) boost::add_vertex(l, uncoloredGraph); 

    add_edge(A, B, EdgeProps{ 1, 1 }, graph);
    add_edge(B, D, EdgeProps{ 2, 3 }, graph);
    add_edge(D, E, EdgeProps{ 3, 1 }, graph);
    add_edge(E, C, EdgeProps{ 4, 7 }, graph);
    add_edge(C, A, EdgeProps{ 5, 1 }, graph);
    add_edge(A, D, EdgeProps{ 6, 2 }, graph);
    add_edge(C, D, EdgeProps{ 7, 2 }, graph);

    //boost::property_map<Sub, boost::edge_weight_t>::type weightmap = boost::get(boost::edge_weight, graph);

    auto make_name_map = [&names](Sub const& s) {
        return boost::make_function_property_map<Vertex>([&](Vertex vd) { return names[s.local_to_global(vd)]; });
    };

    print_graph(graph,          make_name_map(graph),          std::cout << "\ngraph:\n");
    print_graph(coloredGraph,   make_name_map(coloredGraph),   std::cout << "\ncoloredGraph:\n");
    print_graph(uncoloredGraph, make_name_map(uncoloredGraph), std::cout << "\nuncoloredGraph:\n");
}

Отпечатки: 

graph:
A <--> B C D 
B <--> A D 
C <--> E A D 
D <--> B E A C 
E <--> D C 
F <--> 

coloredGraph:
A <--> 
E <--> 
F <--> 

uncoloredGraph:
B <--> D 
C <--> D 
D <--> B C

Почему vertex_index?

Он не используется и, вероятно, приведет к путанице.Я бы предложил просто уронить его: Live On Coliru

...