了解boost :: disjoint_sets

我需要使用boost :: disjoint_sets，但文档不清楚。 有人可以请解释每个模板参数意味着什么，也许给一个小例子代码创build一个disjoint_sets？

根据请求，我使用disjoint_sets来实现Tarjan的离线最小公共祖先algorithm ，即 – 值types应该是vertex_descriptor。

我能从文档中了解到什么：

不相交需要将一个等级和一个父亲（在森林树中）关联到每个元素。 因为你可能想要处理任何types的数据，例如，你可能并不总是想使用父图的地图：使用整数数组就足够了。 你还需要排名敌人的每个元素（工会find所需的排名）。

你需要两个“属性”：

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

举个例子： 

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

数组使用&rank[0], &parent[0]来模板中的types是int*

对于一个更复杂的例子（使用地图），你可以看看Ugo的答案。

你只是给algorithm两个结构来存储他需要的数据（排名/父母）。 

 disjoint_sets<Rank, Parent, FindCompress>
  • Rank PropertyMap用于存储一个集合的大小（element – > std :: size_t）。 按级别查看联盟
  • 父 PropertyMap用于存储元素的父元素（元素 – >元素）。 请参阅path压缩
  • 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）可以在这里find。

对于那些无法负担std::map开销的人（或者因为在类中没有默认构造函数而无法使用它），但是其数据不像int那样简单，我写了一个指南到一个使用std::vector的解决scheme，当您事先知道元素的总数时，这是一种最佳的解决scheme。

该指南包含一个完整的示例代码 ，您可以自行下载和testing。

这里提到的解决scheme假设你有类的代码的控制，所以特别是你可以添加一些属性。 如果这仍然是不可能的，你可以随时添加一个包装： 

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

而且，如果你知道元素的数量很小，就不需要size_t ，在这种情况下，你可以为UnsignedInttypes添加一些模板，并在运行时决定使用uint8_t ， uint16_t ， uint32_t或uint64_t来实例化它，你可以在C ++ 11中用<cstdint>获得，否则用boost::cstdint 。 

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

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

Interesting Posts