如何從Kruskal MST的捆綁特性中獲取重量圖？

我正在嘗試將Kruskal的最小生成樹應用到我的圖中，以將它從無向循環圖變成真正的樹。邊權重都是一樣的，因爲MST是否是唯一的並不重要。如何從Kruskal MST的捆綁特性中獲取重量圖？

到目前爲止如下，我實現它：

typedef boost::adjacency_list<boost::setS, boost::listS, 
      boost::undirectedS, CoordNode, CoordSegment> BGraph;

與

class CoordSegment { 
public: 
    double weight; 
[...] 
}

，我需要一些功能添加到我的圖形，所以我的圖形對象實際上是一種衍生物（如該事項）：

class Graph : public BGraph { 
protected: 
    unsigned int _idCounter; 

[...] 
}

我的問題是在這裏：

// compiles ok 
boost::property_map<BGraph, double CoordSegment::*>::type weightMap = boost::get(&CoordSegment::weight, _graph); 

    std::vector<EdgeDesc> tree; 
// doesn't compile 
    boost::kruskal_minimum_spanning_tree(_graph, std::back_inserter(tree), weightMap);

它抱怨如下：

\src\PGraphSkel.cpp(376) : error C2784: "void boost::kruskal_minimum_spanning_tree(const Graph &,OutputIterator,const boost::bgl_named_params<P,T,R> &)": template-argument for "const boost::bgl_named_params<P,T,R> &" could not be deduced from "boost::bundle_property_map<Graph,Descriptor,Bundle,T>". 
1>  with 
1>  [ 
1>   Graph=BGraph, 
1>   Descriptor=boost::detail::edge_desc_impl<boost::undirected_tag,void *>, 
1>   Bundle=CoordSegment, 
1>   T=double 
1>  ] 
1>  C:\Libraries\boost_1_46_1\boost/graph/kruskal_min_spanning_tree.hpp(120): See declaration of 'boost::kruskal_minimum_spanning_tree'

爲什麼會抱怨呢？

如何才能將我的bundled_property_map轉換爲此Kruskal MST函數所需的正確bgl_named_params參數？

來源

2013-02-07 chaero

從定義的adjacency_list模板類繼承是不是一個好主意。去除這個繼承解決了這個問題。使用boost :: graph作爲一個成員變量，並將其他所有東西封裝在一個類中，會更好。

來源

2013-09-05 07:14:04 chaero

如何從Kruskal MST的捆綁特性中獲取重量圖？

回答

相關問題