理解 boost::disjoint_sets

Question

我需要使用 boost::disjoint_sets，但是 文档 我不清楚。有人可以解释一下每个模板参数的含义，或者给出一个用于创建 disjoint_sets 的小示例代码吗？

根据请求，我使用 disjoint_sets 来实现 Tarjan 的离线最不常见祖先算法，即 -值类型应为 vertex_descriptor。

Answer 1

我从文档中可以理解的是：

不相交的需要将等级和父级（在林树中）与每个元素相关联。例如，由于您可能希望使用任何类型的数据，因此您并不总是希望对父级使用映射：对于整数，数组就足够了。您还需要每个元素的排名（并集查找所需的排名）。

您需要两个“属性”：

• 一个将整数与每个元素关联（第一个模板参数），将
• 一个元素与另一个元素关联（第二个模板参数），父级

在一个示例中：

std::vector<int>  rank (100);
std::vector<int>  parent (100);
boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]);

使用数组 < code>&rank[0], &parent[0] 到模板中的类型是 int*

对于更复杂的示例（使用地图），您可以查看 Ugo 的答案。

您只需为算法提供两个结构来存储他需要的数据（排名/父级）。

Answer 2

disjoint_sets<Rank, Parent, FindCompress>

• Rank PropertyMap 用于存储集合的大小（元素 -> std::size_t）。请参阅按等级联合
• 父级 PropertyMap用于存储元素的父元素（元素->元素）。请参阅路径压缩
• FindCompress 可选定义 find 方法的参数。默认为 find_with_full_path_compression 请参阅此处< /a> （默认值应该是您需要的）。

示例：

template <typename Rank, typename Parent>
void algo(Rank& r, Parent& p, std::vector<Element>& elements)
{
 boost::disjoint_sets<Rank,Parent> dsets(r, p);
 for (std::vector<Element>::iterator e = elements.begin();
      e != elements.end(); e++)
  dsets.make_set(*e);
  ...
}

int main()
{
  std::vector<Element> elements;
  elements.push_back(Element(...));
  ...

  typedef std::map<Element,std::size_t> rank_t; // => order on Element
  typedef std::map<Element,Element> parent_t;
  rank_t rank_map;
  parent_t parent_map;

  boost::associative_property_map<rank_t>   rank_pmap(rank_map);
  boost::associative_property_map<parent_t> parent_pmap(parent_map);

  algo(rank_pmap, parent_pmap, elements);
}

请注意，“Boost 属性映射库包含一些适配器，用于转换实现映射操作的常用数据结构，例如内置数组（指针）、迭代器和 std::map，以具有属性映射接口”

这些适配器的列表（如 boost::associative_property_map）可以在 此处。

Answer 3

对于那些无法承受 std::map 的开销（或者因为类中没有默认构造函数而无法使用它）但数据又不那么简单的人作为int，我写了使用 std::vector 解决方案的指南，当您事先知道元素总数时，这是最佳选择。

该指南包含一个完整工作的示例代码，您可以使用它自行下载并测试。

那里提到的解决方案假设您可以控制类的代码，以便您可以添加一些属性。如果这仍然不可能，您总是可以在它周围添加一个包装器：

class Wrapper {
    UntouchableClass const& mInstance;
    size_t dsID;
    size_t dsRank;
    size_t dsParent;
}

此外，如果您知道元素的数量很小，则不需要 size_t，在这种情况下您可以添加一些模板对于 UnsignedInt 类型，并在运行时决定使用 uint8_t、uint16_t、uint32_t 或 uint64_t 实例化它，您可以通过 在 C++11 中或使用 boost::cstdint 否则。

template <typename UnsignedInt>
class Wrapper {
    UntouchableClass const& mInstance;
    UnsignedInt dsID;
    UnsignedInt dsRank;
    UnsignedInt dsParent;
}

如果您错过了，这里再次提供链接： http://janoma .cl/post/using-disjoint-sets-with-a-vector/

Answer 4

Loic 的答案对我来说看起来不错，但我需要初始化父元素，以便每个元素都有自己作为父元素，因此我使用 iota 函数生成从 0 开始的递增序列。

使用 Boost，我为了简单起见，导入了bits/stdc++.h并使用了usingnamespacestd。

#include <bits/stdc++.h>

#include <boost/pending/disjoint_sets.hpp>
#include <boost/unordered/unordered_set.hpp>
using namespace std;

int main() {
  array<int, 100> rank;
  array<int, 100> parent;

  iota(parent.begin(), parent.end(), 0);
  boost::disjoint_sets<int*, int*> ds(rank.begin(), parent.begin());

  ds.union_set(1, 2);
  ds.union_set(1, 3);
  ds.union_set(1, 4);

  cout << ds.find_set(1) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(2) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(3) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(4) << endl;  // 1 or 2 or 3 or 4
  cout << ds.find_set(5) << endl;  // 5
  cout << ds.find_set(6) << endl;  // 6
}

我将 std::vector 更改为 std::array 因为将元素推送到向量将使其重新分配其数据，这使得不相交集对象包含的引用变得无效。

据我所知，不能保证父级将是一个特定的数字，所以这就是为什么我写了1或2或3或4（可以是其中任何一个）。也许文档更详细地解释了哪个数字将被选为该组的领导者（我还没有研究过）。

就我而言，输出是：

2
2
2
2
5
6

看起来很简单，它可能可以改进以使其更加健壮（以某种方式）。

注意：std::iota 用顺序递增的值填充范围 [first, last)，从 value 开始并重复评估 ++value。
更多：https://en.cppreference.com/w/cpp/algorithm/iota

Answer 5

我不久前写了一个简单的实现。看看吧。

struct DisjointSet {
    vector<int> parent;
    vector<int> size;

    DisjointSet(int maxSize) {
        parent.resize(maxSize);
        size.resize(maxSize);
        for (int i = 0; i < maxSize; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_set(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (size[a] < size[b])
                swap(a, b);
            parent[b] = a;
            size[a] += size[b];
        }
    }
};

用法是这样的。这很简单。不是吗？

void solve() {
    int n;
    cin >> n;
    DisjointSet S(n);  // Initializing with maximum Size
    S.union_set(1, 2);
    S.union_set(3, 7);
    int parent = S.find_set(1);  // root of 1
}