C++ disjoint set

About disjoint set :

C++ 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.
Here we show how to implement a Disjoint List efficiently using C++, and i consider that we already know what a Disjoint List is.
the source code is given below

Just an overview :

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

c++ disjoint set

www.kprblog.in

The main 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,
Core Node : a generic object
Parent Pointer : pointer to the node’s parent in the disjoint list
Childrens :a list of node’s children which we will use to iterate n the whole list

 

Here is the source code of 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  

We must know :
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  

We must know :

  • 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.

Latest posts by admin (see all)

More in sem3
Fibonacci Heap in c++

  Fibonacci Heap in C++ Fibonacci Heap in c++program using struct is given below : #include <iostream> using namespace std;...

Close