59

boost :: disjoint_setsを使用する必要がありますが、ドキュメントがわかりません。誰かが各テンプレートパラメータの意味を説明し、disjoint_setsを作成するための小さなサンプルコードを教えてもらえますか？

リクエストに従って、私はdisjoint_setsを使用して、Tarjanのオフラインで最も一般的でない祖先アルゴリズムを実装しています。つまり、値の型はvertex_descriptorである必要があります。

4

5 に答える 5

21

ドキュメントから理解できること：

Disjointは、ランクと親（フォレストツリー内）を各要素に関連付ける必要があります。あらゆる種類のデータを処理したい場合があるため、たとえば、親にマップを常に使用したい場合はありません。整数の場合は配列で十分です。また、各要素のランク（union-findに必要なランク）も必要です。

2つの「プロパティ」が必要です：

  • 各要素に整数を関連付けるための1つ（最初のテンプレート引数）、ランク
  • 要素を他の要素に関連付けるための1つ（2番目のテンプレート引数）、父親

例：

std::vector<int>  rank (100);
std::vector<int>  parent (100);
boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]);

&rank[0], &parent[0]テンプレートのタイプに使用される配列はint*

より複雑な例（マップを使用）については、Ugoの回答を参照してください。

彼が必要とするデータ（ランク/親）を格納するための2つの構造をアルゴリズムに与えているだけです。

于 2010-11-09T16:31:09.310 に答える
16 
disjoint_sets<Rank, Parent, FindCompress>
  • セットのサイズを格納するために使用されるPropertyMapをランク付けします（要素-> std :: size_t）。ランク別にユニオンを見る
  • 要素の親を格納するために使用される親PropertyMap（要素->要素）。パス圧縮を参照してください
  • FindCompressfindメソッドを定義するオプションの引数。デフォルトでここfind_with_full_path_compressionに表示されます（デフォルトは必要なものである必要があります）。

例：

template <typename Rank, typename Parent>
void algo(Rank& r, Parent& p, std::vector<Element>& elements)
{
 boost::disjoint_sets<Rank,Parent> dsets(r, p);
 for (std::vector<Element>::iterator e = elements.begin();
      e != elements.end(); e++)
  dsets.make_set(*e);
  ...
}

int main()
{
  std::vector<Element> elements;
  elements.push_back(Element(...));
  ...

  typedef std::map<Element,std::size_t> rank_t; // => order on Element
  typedef std::map<Element,Element> parent_t;
  rank_t rank_map;
  parent_t parent_map;

  boost::associative_property_map<rank_t>   rank_pmap(rank_map);
  boost::associative_property_map<parent_t> parent_pmap(parent_map);

  algo(rank_pmap, parent_pmap, elements);
}

「Boostプロパティマップライブラリには、組み込み配列（ポインター）、イテレーター、std :: mapなど、マッピング操作を実装する一般的に使用されるデータ構造を変換して、プロパティマップインターフェイスを持たせるアダプターがいくつか含まれています。」

これらのアダプターのこのリスト（boost ::associative_property_mapなど）はここにあります。

于 2010-11-09T17:23:01.290 に答える
4

オーバーヘッドを支払う余裕がないstd::map（またはクラスにデフォルトのコンストラクターがないために使用できない）が、データがそれほど単純ではない場合はint、を使用してソリューションのガイドstd::vectorを作成しました。これは、要素の総数を事前に知っている場合に最適です。

このガイドには、自分でダウンロードしてテストできる完全に機能するサンプルコードが含まれています。

ここに記載されている解決策は、特にいくつかの属性を追加できるように、クラスのコードを制御できることを前提としています。それでもこれが不可能な場合は、いつでもラッパーを追加できます。

class Wrapper {
    UntouchableClass const& mInstance;
    size_t dsID;
    size_t dsRank;
    size_t dsParent;
}

さらに、要素の数が少ないことがわかっている場合は、の必要はありませんsize_t。その場合、型のテンプレートを追加し、実行時に、、、、またはでUnsignedIntインスタンス化することを決定できます。これは、C++で取得できます。 11またはそれ以外の場合。uint8_tuint16_tuint32_tuint64_t<cstdint>boost::cstdint

template <typename UnsignedInt>
class Wrapper {
    UntouchableClass const& mInstance;
    UnsignedInt dsID;
    UnsignedInt dsRank;
    UnsignedInt dsParent;
}

見逃した場合のリンクは次のとおりです：http：//janoma.cl/post/using-disjoint-sets-with-a-vector/

于 2014-04-02T02:14:01.653 に答える
0

少し前に簡単な実装を書きました。見てください。

struct DisjointSet {
    vector<int> parent;
    vector<int> size;

    DisjointSet(int maxSize) {
        parent.resize(maxSize);
        size.resize(maxSize);
        for (int i = 0; i < maxSize; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_set(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (size[a] < size[b])
                swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

そして、使い方はこんな感じ。簡単だ。ではない？

void solve() {
    int n;
    cin >> n;
    DisjointSet S(n);  // Initializing with maximum Size
    S.union_set(1, 2);
    S.union_set(3, 7);
    int parent = S.find_set(1);  // root of 1
}
于 2021-08-03T10:12:29.297 に答える
0

Loicの答えは私には良さそうですが、各要素がそれ自体を親として持つように親を初期化する必要があったので、このiota関数を使用して0から始まる増加するシーケンスを生成しました。

Boostを使用して、簡単にするためにインポートbits/stdc++.hして使用しました。using namespace std

#include <bits/stdc++.h>

#include <boost/pending/disjoint_sets.hpp>
#include <boost/unordered/unordered_set.hpp>
using namespace std;

int main() {
  array<int, 100> rank;
  array<int, 100> parent;

  iota(parent.begin(), parent.end(), 0);
  boost::disjoint_sets<int*, int*> ds(rank.begin(), parent.begin());

  ds.union_set(1, 2);
  ds.union_set(1, 3);
  ds.union_set(1, 4);

  cout << ds.find_set(1) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(2) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(3) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(4) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(5) << endl;  // 5
  cout << ds.find_set(6) << endl;  // 6
}

要素をベクトルにプッシュするとデータが再割り当てされ、ばらばらのセットオブジェクトに含まれる参照が無効になるため、に変更std::vectorしました。std::array

私の知る限り、親が特定の番号になるとは限らないので、私が書いたのはそのためです1 or 2 or 3 or 4（これらのいずれでもかまいません）。たぶん、ドキュメントは、どの番号がセットのリーダーとして選ばれるかをより詳細に説明しています（私はそれを研究していません）。

私の場合、出力は次のとおりです。

2
2
2
2
5
6

単純なようですが、おそらくそれをより堅牢にするために改善することができます（どういうわけか）。

注：std::iota [最初、最後]の範囲を、値から始めて++値を繰り返し評価して、順番に増加する値で埋めます。 詳細：https：//en.cppreference.com/w/cpp/algorithm/iota

于 2021-12-20T11:35:45.590 に答える