0

ブーストのプリムのアルゴリズムを使用して、エッジの重みだけでなく、エッジの重みと 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)\microsoft visual studio 10.0\vc\include\limits(92): error C2440: '' : cannot convert from 'int' to 'D' 1> No constructor could というエラーが表示されましたソース型を取るか、コンストラクターのオーバーロードの解決があいまいでした」

私はこれを正しい方法でやっていますか？これを行うより良い方法はありますか？

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

編集：わかりましたので、今のところcjmの摂動法を使用して重みを実装しましたが、将来的には上記の方法を何らかの形で使用する必要があると思いますが、どうすればよいかまだ疑問に思っています

edit2: Jeremiah の応答に基づいて、vertex_distance_t を int から EdgeWeight に変更しましたが、同じエラーが発生しました

4

2 に答える 2

2

「Prim の」アルゴリズムの Boost の実装 (Jarník は、Prim のほぼ 30 年前にアルゴリズムを発見しました) は、ダイクストラのアルゴリズムの一般的な実装をサブルーチンとして使用します。誰かがこれは本当に賢いと思ったに違いありません。

ダイクストラのアルゴリズムは、同一性と比較による加算をサポートする非負の重みを必要とし、これらの演算は互換性がなければなりません (すべての x、y、z について、x <= y の場合、x + z <= y + z)。実際には、これらの操作をインスタンス化するための唯一の便利な方法は、通常の方法です(私はこれを取り戻します。ダイクストラのアルゴリズムを同じ方法でタイブレークすることは可能です)。そのため、ダイクストラのアルゴリズムの Boost の実装は、「無限」( std::numeric_limits<vertex_distance_t>::max()) の存在を賢明に想定しています。また、すべての重みが非負であることも表明しています。

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

その結果、Prim のアルゴリズムの Boost の実装では、いくつかの不当な仮定が行われます。次のようにコーディングできますが、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));
}
于 2012-04-14T13:53:17.077 に答える
2

アルゴリズムが機能するには、頂点距離マップvalue_typeがエッジ ウェイト タイプと同じである必要があります。ドキュメントは、( の説明の最初の部分で) ことを暗示してdistance_mapいますが、明示的には述べていません。(この質問に回答してから) Boost トランクのドキュメントを明確にし、修正しました。

于 2012-04-11T20:48:43.307 に答える