多くの要素があり、それらの間の同値関係を追跡する必要があると仮定します。要素Aが要素Bと同等である場合、それは他のすべての要素Bと同等です。
この情報をエンコードするための効率的なデータ構造を探しています。既存の要素との同等性を通じて動的に新しい要素を追加することが可能であり、その情報から、新しい要素が同等であるすべての要素を効率的に計算できる必要があります。
たとえば、要素[0,1,2,3,4]の次の等価セットについて考えてみます。
0 = 1 = 2
3 = 4
ここで、等号は同等性を示します。次に、新しい要素を追加します5
0 = 1 = 2
3 = 4
5
等価性を適用すると5=3
、データ構造は次のようになります。
0 = 1 = 2
3 = 4 = 5
このことから、任意の要素に設定された等価性を効率的に反復できるはずです。5の場合、このセットは[3,4,5]になります。
disjoint_sets
Boostは、私の要件のほとんどを満たしているように見える、と呼ばれる便利なデータ構造をすでに提供しています。上記の例を実装する方法を示すこの単純なプログラムについて考えてみます。
#include <cstdio>
#include <vector>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/unordered/unordered_set.hpp>
/*
Equivalence relations
0 = 1 = 2
3 = 4
*/
int main(int , char* [])
{
typedef std::vector<int> VecInt;
typedef boost::unordered_set<int> SetInt;
VecInt rank (100);
VecInt parent (100);
boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]);
SetInt elements;
for (int i=0; i<5; ++i) {
ds.make_set(i);
elements.insert(i);
}
ds.union_set(0,1);
ds.union_set(1,2);
ds.union_set(3,4);
printf("Number of sets:\n\t%d\n", (int)ds.count_sets(elements.begin(), elements.end()));
// normalize set so that parent is always the smallest number
ds.normalize_sets(elements.begin(), elements.end());
for (SetInt::const_iterator i = elements.begin(); i != elements.end(); ++i) {
printf("%d %d\n", *i, ds.find_set(*i));
}
return 0;
}
上で見たように、要素を効率的に追加し、互いに素な集合を動的に拡張することができます。すべての要素を反復する必要なしに、単一の互いに素なセットの要素を効率的に反復するにはどうすればよいでしょうか。