サンプルの動作確認バージョン [GCC4.4/1.41.0] [VC9/1.41.0]
「Rubyで同値関係を求めるパズル」という記事の例をBoost.Disjoint_setsで書いてみました。
簡単のため「xxx yyy」という空白区切り形式のデータを標準入力からたくさん受け取り、 等しいもの同士をグルーピングして、「xxxx yyyy zzzz ...」のような形式で出力しています。
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <iterator>
#include <algorithm>
#include <boost/pending/disjoint_sets.hpp>
using namespace std;
class Solver
{
public:
void solve( const vector< pair<string,string> >& input )
{
// 入力された名前全てに一意なIDを振る
for(int i=0; i!=input.size(); ++i)
id_of(input[i].first), id_of(input[i].second);
// size()個の要素の同値類分解処理
boost::disjoint_sets_with_storage<> s( size() );
for(int i=0; i!=input.size(); ++i)
// 同じもの同志をunion_setで結合
s.union_set(id_of(input[i].first), id_of(input[i].second));
map< int, vector<string> > equiv;
for(int id=0; id<size(); ++id)
{
// 各要素の同値類の代表元rootを取り出して、それ毎にまとめる
int root = s.find_set(id);
equiv[root].push_back( InverseID[id] );
}
// 表示
for(map< int, vector<string> >::iterator it=equiv.begin(), ed=equiv.end();
it!=ed; ++it)
{
copy( it->second.begin(), it->second.end(),
ostream_iterator<string>(cout, " ") );
cout << endl;
}
}
private:
// IDを振る処理
int id_of( const string& name )
{
if( ID.count(name)==0 )
{
ID[name] = size();
InverseID.push_back(name);
}
return ID[name];
}
int size() const
{
return InverseID.size();
}
map<string, int> ID;
vector<string> InverseID;
};
int main()
{
// 入力
vector< pair<string,string> > input;
for(string x,y; cin>>x>>y; )
input.push_back( make_pair(x,y) );
Solver().solve(input);
}
少女 リズ 少年 ペタ 楽天家 ゲルト 老人 モーリッツ ... (以下略) ...
少女 リズ リーザ リー 少年 ペタ ペーター ペー太 楽天家 ゲルト 老人 モーリッツ 翁 ... (以下略) ...
とまあ、こんな雰囲気で、union_set と find_set メソッドを提供してくれるクラスです。 実装されているのが自然数集合のunionとfindなので、上の例では、文字列をintに手で変換しています。 例では disjoint_sets の完全に外側で int と文字列を変換していますが、 PropertyMap 形式で変換オブジェクトを disjoint_sets に渡すことで、変換操作自体は disjoint_sets に任せることも可能です。 また、最初には全部の要素数がわかっていないような場合、boost::disjoint_sets_with_storage<> ではなく boost::disjoint_sets<> が使えます。
ところで、公式のライブラリ一覧に載ってはいるものの、
置かれているフォルダが boost/pending/ なのはどういうことなんでしょうか。謎です。