Understanding boost :: disjoint_sets

Question

I need to use boost :: disjoint_sets, but the documentation is not clear to me. Can someone explain what each template parameter means, and perhaps give a small code example to create disjoint_sets?

As requested, I use disjoint_sets to implement the Tarjan off-line algorithm of the least common ancestors , i.e. the value type must be vertex_descriptor.

Answer 1

What I can understand from the documentation:

Disjoint needs to associate the rank and parent element (in the forest tree) with each element. Since you can work with any data, you may, for example, not always want to use a map for the parent: with a whole array is enough. You also need the rank of each element (the rank required for a search-union).

You will need two "properties":

• to associate an integer with each element (argument of the first pattern), rank
• to associate an element with another (second argument to the template), fathers

For example:

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

Arrays are used by &rank[0], &parent[0] for the type in the int* template

For a more complex example (using maps) you can see Hugo's answer.

You simply provide the algorithm with two structures for storing the data (rank / parent) that it needs.

Answer 2

 disjoint_sets<Rank, Parent, FindCompress> 

• The PropertyMap rank is used to store the size of the set (element -> std :: size_t). See Ranking
• Parent PropertyMap is used to store the parent element (element -> element). See Compression Path
• FindCompress An optional argument specifying the search method. By default find_with_full_path_compression See here (by default should be what you need).

Example:

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

Please note: “The Boost Properties library contains several adapters that transform commonly used data structures that implement a mapping operation, such as built-in arrays (pointers), iterators, and std :: map to have a property map interface”

This list of these adapters (e.g. boost :: associative_property_map) can be found here .

Answer 3

For those of you who cannot afford the overhead of std::map (or cannot use it because you do not have a default constructor in your class), but whose data is not as simple as int , I wrote a guide to a solution using std::vector , which is optimal when you know the total number of elements in advance.

The manual contains a fully functional sample code that you can download and test yourself.

The solution mentioned here assumes that you control the class code so that in particular you can add some attributes. If this is still not possible, you can always add a wrapper around it:

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

In addition, if you know that the number of elements is small, there is no need for size_t , in which case you can add a template for the UnsignedInt type and solve it at run time using uint8_t , uint16_t , uint32_t or uint64_t , which you can get with using <cstdint> in C ++ 11 or using boost::cstdint otherwise.

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

Here's the link again if you missed it: http://janoma.cl/post/using-disjoint-sets-with-a-vector/