Предположим, у вас много элементов, и вам необходимо отслеживать отношения эквивалентности между ними. Если элемент 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].
Boost уже предоставляет удобную структуру данных под названием disjoint_sets
, которая, по-видимому, отвечает большинству моих требований. Рассмотрим простую программу, которая иллюстрирует, как реализовать приведенный выше пример:
#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;
}
Как видно выше, можно эффективно добавлять элементы и динамически расширять непересекающиеся множества. Как можно эффективно перебирать элементы одного непересекающегося множества, не перебирая все элементы?