c++boostdisjoint-sets

Understanding boost::disjoint_sets


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

As per the request, I am using disjoint_sets to implement Tarjan's off-line least common ancestors algorithm, i.e - the value type should be vertex_descriptor.


Solution

  • What I can understand from the documentation :

    Disjoint need to associate a rank and a parent (in the forest tree) to each element. Since you might want to work with any kind of data you may,for example, not always want to use a map for the parent: with integer an array is sufficient. You also need a rank foe each element (the rank needed for the union-find).

    You'll need two "properties" :

    On an example :

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

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

    For a more complex example (using maps) you can look at Ugo's answer.

    You are just giving to the algorithm two structures to store the data (rank/parent) he needs.