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