Повысить несвязанный набор

Question

Повысить несвязанный набор

Мне нужно сделать несвязный набор типа dataum,

У меня есть все данные в векторе следующим образом

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 должно быть в разных наборах.

1

boost c++disjoint-sets

Решение

Другие решения

Источник

Accepted Answer

В документации говорится, что

Rank должен быть моделью ReadWritePropertyMap с целочисленным типом значения и тип ключа, равный типу элемента набора.
Parent должен быть моделью ReadWritePropertyMap и тип ключа и значения совпадает с типом элемента набора.

На ваш предыдущий вопрос я разместил следующий пример кода в комментарии:

Посмотрев на (новое для меня) disjoint_set_* классы, я не думаю, что они позволяют итерации членов наборов. Они действуют как однонаправленное отображение от элемента к представителю набора. Если это поможет вам: http://paste.ubuntu.com/8881626 — Сехе 9 часов назад

Вот он, переделанный для воображаемого 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));

Механику этого можно найти в документация для Boost PropertyMap, который является очень мощным слоем абстракции общей структуры данных, в основном используется с Boost Graph Library. Это невероятно мощный инструмент, но я не могу сказать, что он удобен для пользователя.

Вот полная демонстрация Жить на Колиру¹

#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";
}

¹ Колиру до сих пор не сотрудничает

2