带提升的最小生成树

Question

我有以下生成无向图的代码：

// --- 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 看到图表）：

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: forming reference to void typedef value_type& reference;，这个错误重复了好几次。出现的其他错误：

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);，但我得到的注释是：

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。很强大，但不容易看懂。

Answer 1

TLDR：使用

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

原回答:

您面临的问题是算法需要访问图的权重图，而您的默认情况下没有。如果您查看 the documentation 中算法的签名，您会发现它是：

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

它有两个 "normal" 参数（您使用的参数），然后是一个看起来很奇怪的 bgl_named_params<P, T, R>& params。最后一个参数允许您使用该页面后面列出的四个参数：weight_map、rank_map、predecessor_map 和 vertex_index_map。如果您不使用这些参数中的任何一个，则使用其默认值，在 weight_map 的情况下，此默认值为 get(edge_weight,g)。仅当您的图形中有内部 edge_weight 属性时才有效，这意味着您的图形定义如下：

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（或任何其他算法），那么 bundled properties 根本就没有用。您只需要使用命名参数覆盖默认值 weight_map：

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

为了访问将 vertex/edge 描述符与您的结构成员相关联的属性映射，您可以简单地使用 get(&Struct::member, g).

关于命名参数的最后一点说明，如果在调用算法时需要使用多个参数，则需要将它们与 . 连接起来，而不是通常的 ,因为在签名中 params 尽管它的名字是一个参数。

//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 是一个示例，它使用内部属性和捆绑属性显示与您想要的内容类似的内容。它故意使用不同的方式 set/access 属性来展示您可以做什么。

带提升的最小生成树

Minimum Spanning Tree with Boost

c++

boost

boost-graph