帶自定義權重的C++ boost prim算法？

Question

我正在嘗試使用boost的prim的算法來找到使用邊權重和id號代替邊緣權重的最小生成樹。

例如，如果兩個邊權重都是1，則會比較id，無論哪一個較少都會打破平局。

我創建了一個EdgeWeight類，並重載了<和+操作符來完成此操作，然後將edge_weight_t屬性從int更改爲EdgeWeight，希望它能夠工作。

// TestPrim.cpp : Defines the entry point for the console application. 
// 

#include "stdafx.h" 

#include <boost/config.hpp> 
#include <iostream> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/prim_minimum_spanning_tree.hpp> 

using namespace std; 

class EdgeWeight{ 
    public: 
    EdgeWeight(){} 
    EdgeWeight(int weightIn, int destinationIdIn){ 
     weight = weightIn; 
     destinationId = destinationIdIn; 
    } 

     bool operator<(const EdgeWeight& rhs) const { 
     if (weight < rhs.weight) 
      return true; 
     else if(weight == rhs.weight){ 
      if (destinationId < rhs.destinationId) 
       return true; 
      else 
       return false; 
     } 
     else 
      return false; 
     } 

    EdgeWeight operator+(const EdgeWeight& rhs) const { 
     EdgeWeight temp; 
     temp.weight = weight + rhs.weight; 
     temp.destinationId = destinationId + rhs.destinationId; 
     return temp; 
     } 

    int weight; 
    int destinationId; 
}; 


int _tmain(int argc, _TCHAR* argv[]) 
{ 
    using namespace boost; 
    typedef adjacency_list < vecS, vecS, undirectedS, property<vertex_distance_t, EdgeWeight>,  property < edge_weight_t, EdgeWeight > > Graph; 
    typedef std::pair < int, int >E; 
    const int num_nodes = 5; 
    E edges[] = { E(0, 2), E(1, 3), E(1, 4), E(2, 1), E(2, 3), 
    E(3, 4), E(4, 0) 
    }; 
    EdgeWeight weights[] = { EdgeWeight(1, 2), EdgeWeight(1, 3), EdgeWeight(2, 4), 
     EdgeWeight(7, 1), EdgeWeight(3, 3), EdgeWeight(1, 4), EdgeWeight(1, 0) }; 
    Graph g(edges, edges + sizeof(edges)/sizeof(E), weights, num_nodes); 
    property_map<Graph, edge_weight_t>::type weightmap = get(edge_weight, g); 
    std::vector < graph_traits <Graph>::vertex_descriptor > p(num_vertices(g)); 
    prim_minimum_spanning_tree(g, &p[0]); 

    for (std::size_t i = 0; i != p.size(); ++i) 
    if (p[i] != i) 
     std::cout << "parent[" << i << "] = " << p[i] << std::endl; 
    else 
     std::cout << "parent[" << i << "] = no parent" << std::endl; 

    return EXIT_SUCCESS; 
} 

我得到一個錯誤，「C：\ Program Files文件（x86）的\微軟的Visual Studio 10.0 \ VC \包括\限制（92）：錯誤C2440：'：詮釋 '到'無法從轉換' D' 1>沒有構造函數可以採取源類型，或構造函數重載分辨率模糊「

我正在做這個正確的方式嗎？有一個更好的方法嗎？

http://www.boost.org/doc/libs/1_38_0/libs/graph/doc/prim_minimum_spanning_tree.html http://www.boost.org/doc/libs/1_38_0/boost/graph/prim_minimum_spanning_tree.hpp

編輯：好了，所以我實現了使用軍事審判的攝動法求現在的權重，但在將來，我相信我會以某種方式使用上述方法，仍然不知道該怎麼辦呢

EDIT2：根據耶利米的效應初探我改變了vertex_distance_t從int到EdgeWeight，但得到了同樣的錯誤

Answer 1

Boost的「Prim's」算法的實現（Jarník在Prim發現差不多30年前就發現了該算法）使用Dijkstra算法的通用實現作爲子程序。我敢肯定有人認爲這是真的很聰明。 Dijkstra的算法需要非負權重來支持帶有標識和比較的加法，並且這些操作必須兼容（對於所有x，y，z，如果x < = y，則x + z < = y + z）。在實踐中，實例化這些操作的唯一有用的方法是習慣的方法（我回過頭來看，可能以同樣的方式將Dijkstra算法打破），所以Boost實現Dijkstra算法明智地假設存在「無窮大」（std::numeric_limits<vertex_distance_t>::max() ）。它還斷言所有權重都是非負的。

相比之下，Prim的算法需要僅支持比較的權重。您可能想知道「最小生成樹」中的「最小值」意味着沒有加法，但最小生成樹的替代特徵是對於從頂點u到頂點v的每條路徑P，P中的最長邊在至少只要樹從u到v的路徑中最長的邊緣。

結果是Boost的Prim算法的實現產生了一些不必要的假設。你可以按如下方式對它們進行編碼，但Boost似乎沒有合同義務在未來不打破這種黑客行爲。

• 擺脫加法運算符;它沒有被使用。

• 由於Boost會斷言你的所有權重都不小於默認構造的值，因此讓我們設置默認的「負無窮大」。

  #include <limits> 
  ... 
  EdgeWeight() : weight(numeric_limits<int>::min()), 
         destinationId(numeric_limits<int>::min()) {} 
  

• 升壓需要 「正無窮大」，所以我們需要專門std::numeric_limits。

  namespace std { 
  template<> 
  struct numeric_limits<EdgeWeight> { 
      static EdgeWeight max() { return EdgeWeight(numeric_limits<int>::max(), 
                 numeric_limits<int>::max()); } 
  }; 
  } 
  

• 您可以簡化比較。

  bool operator<(const EdgeWeight& rhs) const { 
      return (weight < rhs.weight || 
        (weight == rhs.weight && destinationId < rhs.destinationId)); 
  } 
  

Answer 2

的頂點距離地圖的value_type需要與t相同他邊緣權重類型的算法工作。該文件暗示（在distance_map的描述的第一部分），但沒有明確說明。我（自從回答這個問題以來）澄清並更正了Boost主幹中的文檔。