Реализация отношений эквивалентности в C ++ (с использованием boost :: disjoint_sets) - PullRequest
Новая
       46

Реализация отношений эквивалентности в C ++ (с использованием boost :: disjoint_sets)

5 голосов
/ 17 сентября 2010

Предположим, у вас много элементов, и вам необходимо отслеживать отношения эквивалентности между ними. Если элемент 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;
}

Как видно выше, можно эффективно добавлять элементы и динамически расширять непересекающиеся множества. Как можно эффективно перебирать элементы одного непересекающегося множества, не перебирая все элементы?

1 Ответ

2 голосов
/ 09 ноября 2010

Скорее всего, вы не можете сделать это, disjoint_sets не поддерживает итерации только для одного набора. Базовая структура данных и алгоритмы в любом случае не смогут сделать это эффективно, т. Е. Даже если в disjoint_sets будет встроена поддержка итерации только для одного набора, это будет так же медленно, как итерация по всем наборам, и фильтрация неправильные сеты.

...