实现用C的等价关系++（使用boost :: disjoint_sets） [英] Implementing equivalence relations in C++ (using boost::disjoint_sets)

问题描述

假设你有很多元素，你需要保持他们之间的等价关系的轨道。如果元素A相当于元素B，它相当于所有其他元素B是相当于。

Assume you have many elements, and you need to keep track of the equivalence relations between them. If element A is equivalent to element B, it is equivalent to all the other elements B is equivalent to.

我要寻找一个高效的数据结构来连接code此信息。它应该有可能来动态地通过一个等价与现有元件增加新的元素，并从该信息，则应该是可以有效地计算所有元素的新元素等价于。

I am looking for an efficient data structure to encode this information. It should be possible to dynamically add new elements through an equivalence with an existing element, and from that information it should be possible to efficiently compute all the elements the new element is equivalent to.

例如，请考虑以下等价集合的元素[0,1,2,3,4]：

For example, consider the following equivalence sets of the elements [0,1,2,3,4]:

0 = 1 = 2
3 = 4

其中等号表示等价。现在我们添加一个新的元素 5

0 = 1 = 2
3 = 4 
5

和实施的等价 5 = 3 ，数据结构变得

and enforcing the equivalence 5=3, the data structure becomes

0 = 1 = 2
3 = 4 = 5

由此看来，一个人应该能够通过任何元素设置等价有效迭代。 5，这一套是[3,4,5]。

From this, one should be able to iterate efficiently through the equivalence set for any element. For 5, this set would be [3,4,5].

升压已经提供了名为 disjoint_sets方便的数据结构，似乎满足大部分我的要求。考虑这个简单的程序，illustates如何实现上面的例子：

Boost already provides a convenient data structure called disjoint_sets that seems to meet most of my requirements. Consider this simple program that illustates how to implement the above example:

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

就像上​​面说的可以有效地添加元素，并动态扩展不相交集。怎么能有效地在一个单一的一套不相交的元素迭代，而不必遍历所有的元素？

As seen above one can efficiently add elements, and dynamically expand the disjoint sets. How can one efficiently iterate over the elements of a single disjoint set, without having to iterate over all the elements?

推荐答案

最可能的是，你不能这样做， disjoint_sets 不支持超过一只设置迭代。底层的数据结构和算法将无法做到这一点无论如何有效，也就是说即使有内置于 disjoint_sets 迭代超过只设置的支持，这将是就像慢的迭代在所有集，过滤掉错误的集合。

Most probably you can't do that, disjoint_sets doesn't support iteration over one set only. The underlying data structure and algorithms wouldn't be able to do it efficiently anyway, i.e. even if there was support built in to disjoint_sets for iteration over one set only, that would be just as slow as iterating over all sets, and filtering out wrong sets.

这篇关于实现用C的等价关系++（使用boost :: disjoint_sets）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！