Implementing disjoint sets in C++

Implementing disjoint sets in C++ using path compression and union by rank

introduction

Disjoint sets are very useful data structures that are used in many famous Algorithms, and you might consider using them in designing algorithms that include some sort of union behavior.
In this post i will show you how to implement a Disjoint List efficiently using C++, and i consider that you already know what a Disjoint List is.
the source code is attached.

overview

the implementation is as follows,
a disjoint list is a list of disjoint nodes objects, each node is holding a generic node of data_type defined by the user.
Each Disjoint Node has a list of all its childrens.

mian functions are :

• list.unionlist(x), unions the list with list x
• list.find(DisjointNode n), finds the representative (root) of the list holding node n 

The Disjoint Node

the node of our Disjoint list is called DisJointNode and it has the following structure,
CoreNode, a generic object
ParentPointer , pointer to the node's parent in the disjoint list
Childs, a list of node's children which we will use to iterate n the whole list

Here is the DisJointNode.h

 #ifndef DISJOINTNODE_H  
 #define DISJOINTNODE_H  
 #include<list>  
 #include<vector>  
 #include <string>  
 using namespace std;  
 template<class a_type> class DisJointNode {  
 public:  
      a_type coreNode; //input by user contains core info  
      DisJointNode<a_type> *parent; //linking structure  
      std::list<DisJointNode<a_type> *> *childs; //we need this list for iteration and deletion perposes  
      int rank;  
 public:  
      string setName;  
      DisJointNode();  
      DisJointNode(a_type node);  
      void setParent(DisJointNode<a_type>*paren);  
      virtual ~DisJointNode();  
 protected:  
 };  
 ///////////////////////////////////////////////////////////////////////////////////////////  
 template<class a_type> DisJointNode<a_type>::DisJointNode(){  
 }  
 template<class a_type> DisJointNode<a_type>::DisJointNode(a_type node) {  
      this->setName="NONAME";  
      this->coreNode = node;  
      this->parent = NULL;  
      this->rank = 0;  
      this->childs = new std::list<DisJointNode<a_type> *>();  
 }  
 template<class a_type> void DisJointNode<a_type>::setParent(  
           DisJointNode<a_type>*paren) {  
      this->parent = paren;  
 }  
 template<class a_type> DisJointNode<a_type>::~DisJointNode() {    
      delete (childs);  
 }  
 #endif // DISJOINTNODE_H  

Note:
when a Node is created, its initial parent is the node it self.

The DisjointList

A Disjoint list will include pointer to a DisJointNode (root), all the nodes of a given list will be linked to the list's root such that parent of a node is another node in the list or the root of the node,

DisJointList.h

 #ifndef DISJOINLIST_H  
 #define DISJOINLIST_H  
 #include "DisJointNode.h"  
 #include<list>  
 #include <iostream>  
 #include <string>  
 using namespace std;  
 /**  
  we must include the implementation in the header file  
  why? because...what ever iam too lazy to know  
  **/  
 template<class a_type> //indicate a template type to the compiler  
 class DisjoinList {  
 protected:  
 public:  
      string name;  
      DisJointNode<a_type> *root;  
      void getList(std::list<DisJointNode<a_type>*> *input);  
      DisjoinList(DisJointNode<a_type> *root); //make set  
      DisjoinList(); //make set  
      DisJointNode<a_type>* find(DisJointNode<a_type> *x); //find set  
      void unionSets(DisjoinList<a_type> *x); //Union set  
      void Link(DisJointNode<a_type> *x, DisJointNode<a_type> *y,  
                DisjoinList<a_type> *list);  
      virtual ~DisjoinList();  
 private:  
      void getListRecursive(std::list<DisJointNode<a_type>*> *input,  
                DisJointNode<a_type> *root);  
 };  
 ///////////////////////////////////////////////////////////////////////////////////////// cpp  
 template<class a_type>  
 DisjoinList<a_type>::DisjoinList()  
 {  
 }  
 template<class a_type>  
 void DisjoinList<a_type>::getList(std::list<DisJointNode<a_type>*> *input) {  
      //in order traversal  
      getListRecursive(input, this->root);  
 }  
 template<class a_type>  
 void DisjoinList<a_type>::getListRecursive(  
           std::list<DisJointNode<a_type>*> *input, DisJointNode<a_type> *root) {  
      //in order traversal   
      typename std::list<DisJointNode<a_type> *>::iterator it =  
                root->childs->begin();  
      input->push_front(root);  
      for (int i = 0; it != root->childs->end(); ++it) {  
           getListRecursive(input, *it);  
      }  
      return;  
 }  
 /**  
  * constructor, root node is input  
  */  
 template<class a_type>  
 DisjoinList<a_type>::DisjoinList(DisJointNode<a_type> *root)  
 {  
      this->root = root;  
      this->root->parent = this->root;  
 }  
 template<class a_type>  
 void DisjoinList<a_type>::unionSets(DisjoinList<a_type> *x) {  
      Link(this->root, x->root, x);  
 }  
 template<class a_type>  
 DisJointNode<a_type>* DisjoinList<a_type>::find(DisJointNode<a_type> *x) {  
      if (x->parent != x) {  
           x->parent = find(x->parent);  
      }  
      return x->parent;  
 }  
 /**  
  * links two lists by adjusting their roots  
  */  
 template<class a_type>  
 void DisjoinList<a_type>::Link(DisJointNode<a_type> *x, DisJointNode<a_type> *y,  
           DisjoinList<a_type> *list) {  
      if (x->rank > y->rank) {  
           y->parent = x;  
           x->childs->push_front(y); // adding y to x's childs  
           list->root = x;  
      } else {  
           x->parent = y;  
           y->childs->push_front(x); // adding y to x's childs  
           this->root = y;  
      }  
      if (x->rank == y->rank) {  
           (y->rank)++;  
      }  
 }  
 template<class a_type>  
 DisjoinList<a_type>::~DisjoinList() {  
      if (root == NULL)  
                return;  
           std::list<DisJointNode<a_type> *> *nodes;  
           getList(nodes);  
           delete (nodes);  
 }  
 #endif // DISJOINLIST_H  

Note:

• when unioning two lists we must adjust their roots childs and parents 
• getList() makes an inorder traversal on the list's nodes
• Since we are using pass compression the method Find() sets x->parent = find(x->parent) until we reach the root node, this means that when find() is called again on the same node find() will return in O(1).
• when the destructor ~DisjoinList() is called this means that the list is being deleted, at this point we must delete all the nodes of the list