Implementing equivalence relationships in C ++ (using boost :: disjoint_sets)

Question

Suppose you have many elements and you need to track the equivalence relationships between them. If an element A is equivalent to an element B, it is equivalent to all other elements of B equivalent.

I am looking for an efficient data structure to encode this information. It should be possible to dynamically add new elements through equivalence with the existing element, and from this information it should be possible to efficiently calculate all elements equivalent to the new element.

For example, consider the following equivalence sets of elements [0,1,2,3,4]:

0 = 1 = 2 3 = 4 

where the equal sign denotes equivalence. Now add a new item 5

 0 = 1 = 2 3 = 4 5 

and ensuring equivalence 5=3 the data structure becomes

 0 = 1 = 2 3 = 4 = 5 

Thus, iteration can be effectively performed using an equivalence set for any element. For 5, this set will be [3,4,5].

Boost already provides a convenient data structure called disjoint_sets , which seems to fit most of my requirements. Consider this simple program that highlights how to implement the above example:

 #include <cstdio> #include <vector> #include <boost/pending/disjoint_sets.hpp> #include <boost/unordered/unordered_set.hpp> /* Equivalence relations 0 = 1 = 2 3 = 4 */ int main(int , char* []) { typedef std::vector<int> VecInt; typedef boost::unordered_set<int> SetInt; VecInt rank (100); VecInt parent (100); boost::disjoint_sets<int*,int*> ds(&rank[0], &parent[0]); SetInt elements; for (int i=0; i<5; ++i) { ds.make_set(i); elements.insert(i); } ds.union_set(0,1); ds.union_set(1,2); ds.union_set(3,4); printf("Number of sets:\n\t%d\n", (int)ds.count_sets(elements.begin(), elements.end())); // normalize set so that parent is always the smallest number ds.normalize_sets(elements.begin(), elements.end()); for (SetInt::const_iterator i = elements.begin(); i != elements.end(); ++i) { printf("%d %d\n", *i, ds.find_set(*i)); } return 0; } 

As you can see above, you can effectively add elements and dynamically expand disjoint sets. How can you efficiently iterate over the elements of one disjoint set without having to iterate over all the elements?

Answer 1

Most likely, you cannot do this, disjoint_sets does not support iterating over only one set. The underlying data structure and algorithms cannot in any case do this efficiently, that is, even if support were built into disjoint_sets to iterate over only one set, it would be as slow as iterating over all sets, and filtering the wrong sets.