C++ブーストプリムのアルゴリズムはカスタムウェイトを使用していますか？

Question

私はブーストのプリムのアルゴリズムを使用して、エッジ重みと、エッジ重みだけでなく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ました：エラーC2440： '：int型 'に '' から変換することはできません' マイクロソフトのVisual Studio 10.0 \ VCの\ \ \プログラムファイル（x86の）は\限度（92）が含まれ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

編集：[OK]をので、私は今のCJMの摂動法を使用して重みを実施したが、中私は、何とか上記の方法を使用する必要があります信じている未来はまだそれを

EDIT2を行う方法を疑問に思っ：エレミヤのREPONSEに基づいて、私はEdgeWeightにint型からvertex_distance_tを変更したが、同じエラー

Answer 1

Boostの「Prim」アルゴリズムの実装（JarníkはPrimより30年近く前にアルゴリズムを発見しました）は、Dijkstraのアルゴリズムの汎用実装をサブルーチンとして使用します。私は誰かがこれが本当に賢いと思ったと確信しています。

ダイクストラ法は、アイデンティティと比較と追加をサポート非負の重みを必要とし、これらの動作は、（X < = Y、次いでX + Z < = Y + Z場合、すべてのX、Y、Zのための）互換でなければなりません。実際には、 これらの操作をインスタンス化する唯一の便利な方法は、慣習的なものです （私はこれを取り戻します;同じ方法でDijkstraのアルゴリズムを結ぶことは可能です）、BoostのDijkstraのアルゴリズムの実装は "無限"（std::numeric_limits<vertex_distance_t>::max() ）。また、すべての重みは負ではないと主張します。

対照的に、Primのアルゴリズムでは、比較のみをサポートする重みが必要です。 「最小スパニングツリー」の「最小」とは何も追加しないことを意味するかもしれませんが、最小スパニングツリーの別の特徴付けは、頂点uから頂点vまでのすべてのパスPについて、Pの最長エッジは少なくともuからvへのツリーのパスの最長エッジと同じ長さ。

その結果、ブーストのプリムのアルゴリズムの実装では、いくつかの不当な仮定があります。次のようにそれらを囲むことができますが、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トランクの文書を明確にし、修正しました。