Monday, March 16, 2015

Disjoint Sets Tree Implementation [Path Compression+Union by Rank] using HashMap Java

Tutorial: https://www.youtube.com/watch?v=UBY4sF86KEY (10 mins)

Java Implementation (Without Union by Rank and Path Compression):

import java.util.*;

public class DisjointSets {
    private static Map<Character, Character> PARENT;
    
    public static void initialize(char[] universe){ 
        PARENT = new HashMap<>();
        for(char x:universe){
            PARENT.put(x, x);
        } 
    }
    
    public static char Find(char item){
        char parent = PARENT.get(item);
        if(parent==item)return item;
        else return Find(parent);
    }
    
    public static void Union(char setA, char setB){
        PARENT.put(PARENT.get(setA), setB);
    }
    
    public static void main(String[] args) throws Exception{ 
            char universe[] = {'a', 'b', 'c', 'd', 'e'};
            initialize(universe);
            //Set parent of d to b
            Union('d', 'b');
            System.out.println("Item d is in the set "+Character.toUpperCase(Find('d')));
            //Set parent of b to e
            Union('b', 'e');
            System.out.println("Item d is in the set "+Character.toUpperCase(Find('d')));
    } 
}

Output:

Item d is in the set B
Item d is in the set E

Implementation With Union By Rank (attach lesser rank node to greater one) and Path Compression (Union of roots):

import java.util.*;

public class DisjointSetsUnionByRankPathCompression{
    private static Map<Character, Character> PARENT;
    private static Map<Character, Integer> RANKS; //to store the depths
    
    public static void initialize(char[] universe){ 
        PARENT = new HashMap<>();
        RANKS = new HashMap<>();
        for(char x:universe){
            PARENT.put(x, x);
            RANKS.put(x, 1);
        } 
    }
    
    public static char Find(char item){
        char parent = PARENT.get(item);
//        System.out.println("Finding the parent of "+item+" is: "+parent);
        if(parent==item)return item;
        else return Find(parent);
    }
    
    public static void Union(char setA, char setB){
        char pA, pB;
        while((pA = PARENT.get(setA))!=setA){setA = pA;}
        while((pB = PARENT.get(setB))!=setB){setB = pB;}
        
        int rankFirst = RANKS.get(setA), rankSecond = RANKS.get(setB);
        if(rankFirst>rankSecond){
            PARENT.put(setB, setA); 
            System.out.println("\nRank of "+setA+" is greater than that of "+setB);
            System.out.println("Setting the parent of "+setB+" to "+setA);
            updateRanksUpward(setB);
        }else if(rankSecond>rankFirst){
            PARENT.put(setA, setB); 
            System.out.println("\nRank of "+setB+" is greater than that of "+setA);
            System.out.println("Setting the parent of "+setA+" to "+setB);
            updateRanksUpward(setA);
        }else{
            PARENT.put(setB, setA);
            System.out.println("\nBoth "+setA+" and "+setB+" have same Ranks");
            System.out.println("Setting the parent of "+setB+" to "+setA);
            updateRanksUpward(setB);
        }
    }
    
    public static void updateRanksUpward(char current){
        int currentDepth = RANKS.get(current);
        char currentsParent = PARENT.get(current);
        int parentsDepth = RANKS.get(currentsParent);
        if(!(currentDepth<parentsDepth || currentsParent == current)){
            System.out.println("Update rank of "+currentsParent+" by child "+current);
            RANKS.put(currentsParent, currentDepth+1);
            updateRanksUpward(currentsParent);
        }
    }
    
    public static void main(String[] args) throws Exception{
            char universe[] = {'a', 'b', 'c', 'd', 'e'};
            initialize(universe);
            
            //Set parent of d to b
            Union('d', 'b');
            System.out.println("Item b is in the set "+Character.toUpperCase(Find('b')));
            System.out.println(PARENT);
            System.out.println(RANKS);
            
            //Set parent of b to e
            Union('b', 'e');
            System.out.println("Item e is in the set "+Character.toUpperCase(Find('e')));
            System.out.println(PARENT);
            System.out.println(RANKS);
            
            //Find the set of a
            System.out.println("Item a is in the set "+Character.toUpperCase(Find('a')));
            System.out.println(PARENT);
            System.out.println(RANKS); 
            
            //Test 2
            initialize(new char[]{'a','e','l','i','d','b','e'});
            Union('a', 'e');
            Union('e', 'l');
            Union('l', 'i');
            
            Union('d', 'b');
            Union('b', 'e'); //(Unite the two sets that is union(a, d) - unite both sets
            
            System.out.println(PARENT);
            System.out.println(RANKS); 
            
    }
}

Output:

Both d and b have same Ranks
Setting the parent of b to d
Update rank of d by child b
Item b is in the set D
{a=a, b=d, c=c, d=d, e=e}
{a=1, b=1, c=1, d=2, e=1}

Rank of d is greater than that of e
Setting the parent of e to d
Item e is in the set D
{a=a, b=d, c=c, d=d, e=d}
{a=1, b=1, c=1, d=2, e=1}
Item a is in the set A
{a=a, b=d, c=c, d=d, e=d}
{a=1, b=1, c=1, d=2, e=1}

Both a and e have same Ranks
Setting the parent of e to a
Update rank of a by child e

Rank of a is greater than that of l
Setting the parent of l to a

Rank of a is greater than that of i
Setting the parent of i to a

Both d and b have same Ranks
Setting the parent of b to d
Update rank of d by child b

Both d and a have same Ranks
Setting the parent of a to d
Update rank of d by child a
{a=d, b=d, d=d, e=a, i=a, l=a}
{a=2, b=1, d=3, e=1, i=1, l=1}

No comments:

Post a Comment