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.
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.
disjoint_sets<Rank, Parent, FindCompress>
find_with_full_path_compression
See here (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);
}
Note that "The Boost Property Map Library contains a few adaptors that convert commonly used data-structures that implement a mapping operation, such as builtin arrays (pointers), iterators, and std::map, to have the property map interface"
This list of these adaptors (like boost::associative_property_map) can be found here.
For those of you who can't afford the overhead of std::map
(or can't use it because you don't have 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 kind of optimal when you know the total number of elements beforehand.
The guide includes a fully-working sample code that you can download and test on your own.
The solution mentioned there assumes you have control of 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;
}
Moreover, if you know the number of elements to be small, there's no need for size_t
, in which case you can add some template for the UnsignedInt
type and decide in runtime to instantiate it with uint8_t
, uint16_t
, uint32_t
or uint64_t
, which you can obtain with <cstdint>
in C++11 or with boost::cstdint
otherwise.
template <typename UnsignedInt>
class Wrapper {
UntouchableClass const& mInstance;
UnsignedInt dsID;
UnsignedInt dsRank;
UnsignedInt dsParent;
}
Here's the link again in case you missed it: http://janoma.cl/post/using-disjoint-sets-with-a-vector/
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With