带Boost的最小生成树 [英] Minimum Spanning Tree with Boost

问题描述

我有以下代码生成无向图:

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

问题出在我称之为Kruskal的一行中: kruskal_minimum_spanning_tree().如果我对此行发表评论，它将可以正常编译，并且可以使用graphviz导出图形(您可以在 webgraphviz.com ):

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];
}

但是，如果我尝试使用该行进行编译，我会从Boost中得到很多错误(我使用的是g ++ 4.9.2).第一个错误是: error:形成对void typedef value_type&的引用.参考； ，此错误会重复多次.出现的其他错误:

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

因此，在调用Kruskal方法之前，我尝试添加 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));

和

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

我不知道该怎么办.这是我第一次使用Boost Graph Library.它功能强大，但不容易理解.

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.

推荐答案

TLDR :使用

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

原始答案:

您面临的问题是该算法需要访问图表的权重图，而默认情况下您的算法没有权重图.如果您在文档中查看算法的签名，您会看到就是这样:

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

它有两个常规"参数(您使用的参数)，然后是一个看起来奇怪的 bgl_named_pa​​rams< P，T，R>&参数.最后一个参数允许您使用该页面后面列出的四个参数: weight_map ， rank_map ， predecessor_map 和 vertex_index_map .如果您不使用这些参数中的任何一个，则使用其默认值；如果是 weight_map ，则默认值为 get(edge_weight，g).仅当您的图形中具有一个内部edge_weight属性时，该方法才有效，这意味着您的图形是这样定义的:

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;

但是如果使用 kruskal_minimum_spanning_tree (或任何其他算法)需要该定义，则

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

为了访问将顶点/边缘描述符与结构成员相关联的属性映射，您可以简单地使用 get(& Struct :: member，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).

关于命名参数的最后说明，如果在调用算法时需要使用多个这些参数，则需要将它们与串联.，而不是通常的，，因为尽管其名称是单个参数，但在签名 params 中.

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.

这篇关于带Boost的最小生成树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！