BGL get weight map for graph

Question

I would like to implement weighted undirected graph with the subgraphs. Here is my initialization code for that graph:

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

Now i want to get the weight map for Dijkstra algo, and try to use the code:

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

But compiler error occurs:

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

I have a suggestion that the subgraph works wrong with bundled properties, but using internal member of class UndirectedGraphS of type UndirectedGraph leads to same error. Please, tell me what going wrong with template instantiation

Answer 1

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

defines EdgeWeightProperty as the Graph Property. Instead you want both an edge index and weight:

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

And use them both for the edge:

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

Now you can simply boost::get(boost::edge_weight, g), e.g.:

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

Several other issues:

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

This accidentally creates a useless copy for uncoloredGraph:

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

Prevent that by being more explicit:

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

Lots of things can (and should) be simpler:

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

Adding name maps, printing the graphs

Just for a feeling of how the graphs end up:

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

Prints:

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 

Why vertex_index?

It's not used and will probably lead to a lot of confusion. I'd suggest to just drop it: Live On Coliru