了解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用于存储集合的大小(element - > std :: size_t).按等级查看联合
• Parent PropertyMap用于存储元素的父元素(element - > element).请参阅路径压缩
• FindCompress定义find方法的可选参数.默认为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).