我需要创建一个 dataum
类型的不相交集。
我有 vector 中的所有数据如下
vector<dataum> S;
S.push_back( dataum(0,0) );
S.push_back( dataum(0,1) );
S.push_back( dataum(0,2) );
.
.
然后我创建了 disjoint_set
std::vector<int> rank (100);
std::vector<dataum> parent (100);
boost::disjoint_sets<int*,dataum*> ds(&rank[0], &parent[0]);
for( int i=0 ; i<S.size() ; i++ )
{
ds.make_set( S[i] );
}
这似乎行不通。我错过了什么?
我想创建一个具有自定义数据类型的不相交集。在这种情况下 dataum
。最初我的每个 dataums
应该在不同的集合中。
最佳答案
文档指出
Rank
必须是ReadWritePropertyMap
的模型,具有整数值类型并且键类型等于集合的元素类型。Parent
必须是ReadWritePropertyMap
的模型,并且键和值类型与集合的元素类型相同。
在您之前的问题中,我在评论中发布了以下示例代码:
After looking at the (new for me)
disjoint_set_*
classes, I don't think that they afford iterating members of sets. They act like unidirectional mapping from element to set representative. In case it helps you: http://paste.ubuntu.com/8881626 – sehe 9 hours ago
在这里,为想象中的 dataum
类型重新设计:
struct dataum {
int x,y;
bool operator< (const dataum& o) const { return tie(x,y) < tie(o.x,o.y); }
bool operator==(const dataum& o) const { return tie(x,y) == tie(o.x,o.y); }
bool operator!=(const dataum& o) const { return tie(x,y) != tie(o.x,o.y); }
};
这是我如何看到它的 disjoint_set
声明:
std::map<dataum,int> rank;
std::map<dataum,dataum> parent;
boost::disjoint_sets<
associative_property_map<std::map<dataum,int>>,
associative_property_map<std::map<dataum,dataum>> > ds(
make_assoc_property_map(rank),
make_assoc_property_map(parent));
这方面的机制可以在 documentation for Boost PropertyMap 中找到。 ,这是一个非常强大的通用数据结构抽象层,主要与 Boost Graph Library 一起使用。它非常强大,但我不能说它对用户友好。
这是完整的演示 Live On Coliru¹
#include <boost/pending/disjoint_sets.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <iostream>
#include <map>
#include <cassert>
using namespace boost;
struct dataum {
int x,y;
bool operator< (const dataum& o) const { return tie(x,y) < tie(o.x,o.y); }
bool operator==(const dataum& o) const { return tie(x,y) == tie(o.x,o.y); }
bool operator!=(const dataum& o) const { return tie(x,y) != tie(o.x,o.y); }
};
int main() {
std::vector<dataum> S { {0,0}, {0,1}, {0,2} };
std::map<dataum,int> rank;
std::map<dataum,dataum> parent;
boost::disjoint_sets<
associative_property_map<std::map<dataum,int>>,
associative_property_map<std::map<dataum,dataum>> > ds(
make_assoc_property_map(rank),
make_assoc_property_map(parent));
for(auto i=0ul; i<S.size(); i++)
ds.make_set(S[i]);
assert((ds.count_sets(S.begin(), S.end()) == 3));
assert((ds.find_set(dataum{0,2}) == dataum{0,2}));
assert((ds.find_set(dataum{0,1}) == dataum{0,1}));
ds.union_set(dataum{0,2},dataum{0,1});
assert((ds.count_sets(S.begin(), S.end()) == 2));
assert((ds.find_set(dataum{0,2}) == dataum{0,1}));
assert((ds.find_set(dataum{0,1}) == dataum{0,1}));
std::cout << "done";
}
¹ Coliru 仍然不合作
关于c++ - Boost分离集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26814780/