c++ - 理解 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]);

数组用于&rank[0], &parent[0]模板中的类型是int*

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

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

Answer 2

disjoint_sets<Rank, Parent, FindCompress>

• Rank PropertyMap 用于存储集合的大小（元素 -> std::size_t）。按等级查看工会
• Parent PropertyMap 用于存储元素的父级（元素 -> 元素）。请参见路径压缩
• FindCompress定义查找方法的可选参数。默认在此处查看find_with_full_path_compression（默认应该是您需要的）。

例子：

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可以在C++ 中使用11 或以其他方式。uint32_tuint64_t<cstdint>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并使用using namespace std了。

#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 or 2 or 3 or 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
}