了解boost :: disjoint_sets

我需要使用boost :: disjoint_sets，但the documentation对我来说还不清楚。有人可以解释一下每个模板参数的含义吗，也许可以给出一个创建disjoint_sets的小例子代码？了解boost :: disjoint_sets

根据请求，我使用disjoint_sets来实现Tarjan's off-line least common ancestors algorithm，即 - 值类型应该是vertex_descriptor。

来源

2010-11-09 Amir Rachum

这可能会更好地工作，如果你提供你想要达到什么样的一个例子。 – 2010-11-09 15:00:49

+13

哇，看起来好像很多人好奇，没有多少人知道如何开始使用它。 – wheaties 2010-11-09 15:05:35

至少有一个在SO上使用的简单示例：http://stackoverflow.com/questions/3738537/implementing-equivalence-relations-in-c-using-boostdisjoint-sets – Cubbi 2010-11-09 15:23:10

我可以从文档明白什么：

脱节需要一个等级和家长（在林木）给每个元素相关联。因为你可能想要处理任何类型的数据，例如，你可能并不总是希望为父对象使用一个映射：对于整数来说，一个数组就足够了。你还需要排名敌人每个元素（工会发现所需的排名）。

你需要两个“属性”：

一个对每个元素的整数（第一个模板参数），秩
一个到另一个的元素相关联（第二模板关联参数），父亲

在一个示例：

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的答案。

你只是给算法两个结构来存储他需要的数据（等级/父）。

来源

2010-11-09 16:31:09

如果你不知道以前的最大元素数量，还有比地图更简单的解决方案吗？ – 2016-07-11 14:50:00

disjoint_sets<Rank, Parent, FindCompress>

排名属性映射用来存储一组的大小（元素 - >的std ::的size_t）。请参见union by rank
父 PropertyMap用于存储元素（元素 - >元素）的父项。请参阅Path compression
FindCompress定义find方法的可选参数。默认为find_with_full_path_compression请参阅here（默认应该是你需要的）。

实施例：

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

注意，“升压属性映射库包含转换常用的数据结构实现的映射操作，诸如内置阵列（指针），迭代数适配器，和std :: map，以获得属性映射接口“

这些适配器的列表（如boost :: associative_property_map）可以找到here。

来源

2010-11-09 17:23:01 log0

真的很好的解释。我会删除我的答案。 – 2010-11-10 14:18:07

@Loic其实你的答案是完成这一个。因为如果元素== int（使用矢量），可以使用更高效的代码。 – log0 2010-11-10 15:00:17

好的。然后我将删除第二个示例。 – 2010-11-10 15:19:05

对于那些无法负担std::map（或因为您的班级中没有默认构造函数而无法使用它）的开销，但其数据并不像int那么简单，我写了a guide到使用std::vector的解决方案，当您事先知道元素的总数时，这种解决方案是最佳的。

该指南包含一个fully-working sample code，您可以自行下载和测试。

这里提到的解决方案假设您已经控制了类的代码，因此您可以添加一些属性。如果这仍然是不可能的，你可以随时添加一个包装周围：

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中使用<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/

来源

2014-04-02 02:14:01 Janoma

了解boost :: disjoint_sets

回答

相关问题