Algorithm Lab Assignment 7
NAME – RIJU CHAKRABORTY
ROLL NO. – GCECTB-R20-3020
DEPT. – CSE
Q:- Implement union find algorithm using linked list, ranked linked list
and tree representations on a disjoint set of size n. Perform m operations
on each structure, where the first n operations are makeset operations,
the rest are findset or union operations. The union stops once there is
only one set present. If there is only one set present remaining
operations are all findset operations. Calculate the number of
comparisons required to perform the m operations. Plot a graph of no. of
comparisons vs m. For n=100, m=200,300,
500,1000,1200,1500,1800,2000,2400,2800,3000.
Code:- (Written in C)
1. For Disjoint Set using ranked and unranked Linked list
#include<stdio.h>
#include<stdlib.h>
int cmpur=0; //no. of comparisions for unranked ll
int cmpr=0; //no. of comparisions for ranked ll
int totalSets=100;
struct node{
int data;
struct node *head;
struct node *next;
struct node *tail;
int rank;
}*storeAd[100];
void makeSet(int n){
struct node *newSet;
newSet=(struct node*)malloc(sizeof(struct node));
newSet->data=n;
newSet->next=NULL;
newSet->head=newSet;
newSet->tail=newSet;
newSet->rank=1;
storeAd[n]=newSet->head;
cmpur++;
cmpr++;
}
struct node* findSet(int n){
cmpur++;
cmpr++;
return storeAd[n];
}
void unionUR(int x, int y){
struct node *xh = findSet(x);
struct node *yh = findSet(y);
if(xh!=yh){
struct node *t;
t=yh;
// printf("\nappending at : %d",xh->tail->data);
xh->tail->next=yh->head;
while(t!=NULL){
t->head=xh;
// printf("\n%d : %d",t->data,t->head->data);
int yc=t->data;
storeAd[yc]=t->head;
xh->tail=t;
// printf("\nTail is : %d",t->tail->data);
t=t->next;
cmpur++;
}
totalSets--;
}
printf("\n%d: cmp %d",totalSets,cmpur);
}
void unionR(int x, int y){
struct node *xh = findSet(x);
struct node *yh = findSet(y);
if(xh!=yh){
struct node *t;
struct node *b;
// printf("\nranks xh %d yh %d",xh->rank,yh->rank);
t=(yh->rank <= xh->rank)? yh:xh;
b=(yh->rank <= xh->rank)? xh:yh;
b->tail->next=t->head;
while(t!=NULL){
t->head=b;
// printf("\n%d : %d",t->data,t->head->data);
int yc=t->data;
storeAd[yc]=t->head;
b->tail=t;
b->rank++;
t=t->next;
cmpr++;
}
// free(yh);
totalSets--;
}
printf("\n%d: cmp %d",totalSets,cmpr);
}
void displaySet(int n){
struct node *t= findSet(n);
printf("\n");
while(t!=NULL){
printf(" %d,",t->data);
t=t->next;
}
}
int main(){
int i;
int noop=0;
for(i=0;i<100;i++){
storeAd[i]=NULL;
}
//making 100 disjoint sets
for(i=0;i<100;i++){
makeSet(i);
// printf("%p\n",storeAd[i]);
}
// printf("\nNo. of comparisions for unranked ll - ");
// while(totalSets!=1){
// int p=rand()%100;
// int q=rand()%100;
// if(p!=q){
// printf("\nop-%d",noop);
// unionUR(p,q);
// noop++;
// }
// }
// printf("\n%d",cmpur);
// printf("\nNo. of operations: %d",noop);
printf("\nNo. of comparisions for ranked ll - ");
while(totalSets!=1){
int p=rand()%100;
int q=rand()%100;
if(p!=q){
printf("\nop-%d",noop);
unionR(p,q);
noop++;
}
}
printf("\n%d",cmpr);
printf("\nNo. of operations: %d",noop);
return 0;
}
2. For Disjoint Set using Tree
#include<stdio.h>
#include<conio.h>
int cmpt=0;
int totalSets=100;
struct node{
struct node *parent;
int data;
int rank;
}*storeAd[100];
void makeSet(int n){
struct node *newSet;
newSet=(struct node*)malloc(sizeof(struct node));
newSet->data=n;
newSet->parent=newSet;
newSet->rank=0;
storeAd[n]=newSet->parent;
cmpt++;
}
struct node *root;
struct node* findSet(int n){
struct node *t=storeAd[n];
if(t->parent==t){
// cmpt++;
root=storeAd[n];
return storeAd[n];
}
else{
cmpt++;
findSet(t->parent->data);
t->parent=root;
}
}
void unionT(int x, int y){
struct node *xr = findSet(x);
struct node *yr = findSet(y);
if(xr!=yr){
if(xr->rank > yr->rank){
yr->parent=xr;
}
else if(xr->rank < yr->rank){
xr->parent=yr;
}
else if(xr->rank==yr->rank){
yr->parent=xr;
xr->rank++;
}
cmpt++;
totalSets--;
// printf("\nsets: %d , comp: %d",totalSets,cmpt);
}
}
int main(){
int i;
int noop=0;
for(i=0;i<100;i++){
storeAd[i]=NULL;
}
//making 100 disjoint sets
for(i=0;i<100;i++){
makeSet(i);
// printf("%p\n",storeAd[i]);
}
printf("\nNo. of comparisions for tree - ");
while(totalSets!=1){
int p=rand()%100;
int q=rand()%100;
if(p!=q){
// printf("\nop- %d %d,%d",noop,p,q);
unionT(p,q);
noop++;
}
}
printf("\n%d",cmpt);
printf("\nNo. of operations: %d",noop);
for(i=0;i<2800;i++){ //change
int p=rand()%100;
struct node *f=findSet(p);
}
printf("\nno. of comp after remaing no of findset operations- %d",cmpt);
return 0;
}
Output:-
No of 200 300 500 1000 1200 1500 1800 2000 2400 2800 3000
operations
Unranked 950 1796 2132 2632 2832 3132 3432 3632 4032 4432 4632
Ranked 454 670 908 1408 1608 1908 2208 2408 2808 3208 3408
tree 304 369 493 791 911 1095 1263 1371 1586 1821 1947
Graph:-