Minimum Spanning Tree with Boost

Question

I have the following code that generates an undirected graph:

// --- Header File ---
class Node { ... };
struct Edge { float weight; };
typedef adjacency_list<vecS, vecS, undirectedS, Node, Edge> Grafo;

class MST
{
    public:
        MST(std::vector<Node> nodes);
        Grafo g;
        vector<edge_t> build();
};

// --- cpp File ---
MST::MST(std::vector<Node> nodes) {  // build the graph by setting vertices and edges...  }

vector<edge_t> MST::build()
{
    vector<edge_t> mst;
    kruskal_minimum_spanning_tree(g, std::back_inserter(mst));
    return mst;
}

The problem is in the line that I call Kruskal: kruskal_minimum_spanning_tree(). If I comment this line it will compile fine, and I can export the graph with graphviz (you can see the graph at webgraphviz.com):

graph G {
0[label="a"];
1[label="b"];
2[label="c"];
3[label="d"];
4[label="e"];
0--1 [label=80.4487381];
0--2 [label=406.060333];
0--3 [label=405.738831];
0--4 [label=434.203857];
1--2 [label=25.9422436];
1--3 [label=210.344955];
1--4 [label=246.965591];
2--3 [label=35.805027];
2--4 [label=35.1283379];
3--4 [label=167.5858];
}

But if I try to compile with that line I get A LOT of errors from Boost (I'm using g++ 4.9.2). The first error is: error: forming reference to void typedef value_type& reference;, this error repeats several times. Other error that appears:

error: no matching function for call to 'get(boost::edge_weight_t, const boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Symbol, Edge>&)'
        get(edge_weight, g));

So I've tried to add get(edge_weight, g); before call the Kruskal method, but I got notes saying:

note:   types 'boost::subgraph<Graph>' and 'const boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, Symbol, Edge>' have incompatible cv-qualifiers
        get(edge_weight, g));

and

note:   mismatched types 'const boost::two_bit_color_map<IndexMap>' and 'boost::edge_weight_t'
        get(edge_weight, g));

I don't know what to do. This is the first time I'm using Boost Graph Library. It is very powerful but not easy to understand.

Answer 1

TLDR: use

kruskal_minimum_spanning_tree(g, std::back_inserter(mst), 
                        weight_map( get(&Edge::weight, g) );

Original answer:

The problem you are facing is that the algorithm needs to access a graph's weight map and yours doesn't have one by default. If you look at the signature of the algorithm in the documentation you can see that it is:

template <class Graph, class OutputIterator, class P, class T, class R>
OutputIterator kruskal_minimum_spanning_tree(Graph& g, OutputIterator tree_edges, 
                                   const bgl_named_params<P, T, R>& params = all defaults);

It has two "normal" parameters (the ones you used) and then a strange looking bgl_named_params<P, T, R>& params. This last parameter allows you to use the four parameters listed later in that page: weight_map, rank_map, predecessor_map and vertex_index_map. If you don't use any of these parameters its default value is used and in the case of weight_map this default is get(edge_weight,g). That only works if you have an interior edge_weight property in your graph, meaning your graph is defined like this:

typedef adjacency_list<vecS, vecS, undirectedS, 
                    property<vertex_name_t,char>,//Could also be `Node` unless you use another algorithm with requirements on the vertices
                    property<edge_weight_t,float> 
                  > InternalPropGraph;

But if that definition was required to use kruskal_minimum_spanning_tree (or any other algorithm) then bundled properties wouldn't be useful at all. You just need to override the default weight_map using the named parameters:

//typedef adjacency_list<vecS, vecS, undirectedS, Node, Edge> Grafo;
...
kruskal_minimum_spanning_tree(g, std::back_inserter(mst), 
                        weight_map( get(&Edge::weight, g) );

In order to access a property map that relates a vertex/edge descriptor with a member of your structs you can simply use get(&Struct::member, g).

A final note about Named Parameters, if in your invocation of the algorithm you need to use more than one of these parameters, you need to concatenate them with . instead of the usual , since in the signature params despite its name is a single parameter.

//the order of the named params is irrelevant
kruskal_minimum_spanning_tree(g, std::back_inserter(mst), 
                                 weight_map(my_weights)
                                .vertex_index_map(my_indices)
                                .predecessor_map(my_predecessors));

Here is an example that shows something similar to what you want using both internal properties and bundled properties. It deliberately uses different ways to set/access properties to show what you can do.