Home > Frameworks > boost::disjoint_sets

boost::disjoint_sets

Reading head on the documentation of this framework, it became quickly obvious I was in trouble: I had no idea what a disjoint set was in the first place.  So I did some googling, and without surprise, I found the Wikipedia page to be the most understandable and helpful to give me a good overview.

From what I understand, a disjoint sets data structure is a collection of different sets (which are typically linked lists, but there’s also a variant using trees called a disjoint sets forest).  A value can only exist in one of the sets, that is, there can’t be any duplications between sets.  The sets are identified by one of its value, which one could be arbitrary, and called the set representative.

The two most common operations on a disjoint sets are:

  1. Find : look for a specific value in all sets and if found, return the representative of the set it has been found in.
  2. Union : allow the merging of two sets into a single one.  The representatives are used to specify which sets needs to be merged.

Typically there’s a third, minor operation called MakeSet which consist of creating a new set containing a single value (also known as singleton).

The real-life application of a disjoint sets elude me a little.  Apparently it is mostly used in solving partitioning and graph problems.  As a matter of fact, this boost framework is extensively used by another framework, the Boost Graph.

The boost::disjoint_sets implementation is relatively simple and straightforward.  I will not dig unnecessarily into it, considering its very limited potential usage in my day to day programming.  Although I’m glad I now know what a disjoint sets is, if I ever have to deal with them.

Advertisements
Categories: Frameworks
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: