Massive Algorithms: Union-Find - Disjoint-set data structure

Union-Find - Disjoint-set data structure

A union–find algorithm is an algorithm that performs two useful operations on such a data structure:

Find: Determine which subset a particular element is in. This can be used for determining if two elements are in the same subset.
Union: Join two subsets into a single subset.

The Disjoint-set data structure allows us to very quickly determine if two items are in the same set, and also to very quicklyunite two sets.

Java code from http://algs4.cs.princeton.edu/15uf/UF.java.html
http://www.cs.waikato.ac.nz/~bernhard/317/source/graph/UnionFind.java

public class UF {
    private int[] id;     // id[i] = parent of i
    private byte[] rank;  // rank[i] = rank of subtree rooted at i (cannot be more than 31)
    private int count;    // number of components
    public UF(int N) {
        if (N < 0) throw new IllegalArgumentException();
        count = N;
        id = new int[N];
        rank = new byte[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
            rank[i] = 0;
        }
    }
    /* Returns the component identifier for the component containing site */
    public int find(int p) {
        if (p < 0 || p >= id.length) throw new IndexOutOfBoundsException();
        while (p != id[p]) {
            id[p] = id[id[p]];    // path compression by halving
            p = id[p];
        }
        return p;
    }
    public int count() {
        return count;
    }
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
  // The implementation looks suspicious, as when union, it does't change the rank
    public void union(int p, int q) {
        int i = find(p);
        int j = find(q);
        if (i == j) return;

        // make root of smaller rank point to root of larger rank
        if      (rank[i] < rank[j]) id[i] = j;
        else if (rank[i] > rank[j]) id[j] = i;
        else {
            id[j] = i;
            rank[i]++;
        }
        count--;
    }

Code from http://codingrecipies.blogspot.com/2013/09/kruskals-algorithm_17.html

public void Union(int v1, int v2) {
  int i = Find(v1);
  int j = Find(v2);

  if (i == j)
   return;

  if (nodeHolder[i].rank < nodeHolder[j].rank) {
   nodeHolder[i].parent = j;
   nodeHolder[j].rank = nodeHolder[j].rank + nodeHolder[i].rank;
  } else {
   nodeHolder[j].parent = i;
   nodeHolder[i].rank = nodeHolder[i].rank + nodeHolder[j].rank;
  }
  count--;
 }

In its simplest form, the data structure is just an array of integers, called $\textrm{parent}$ . If we are dealing with $n$ items, then $\textrm{parent}$ is an array of size $n$ , and the $i$ th element of the array represents the $i$ th item. More precisely, the $i$ th element of the array is the parent of the $i$ th item.

Each tree is a disjoint set. If two elements are in the same tree, then they are in the same disjoint set. The root node (or the topmost node) of each tree is called the representative of the set. There is always a single unique representative of each set. As you can see, if $i$ is the representative of a set, then $\textrm{parent[}i\textrm{]} = i$ . If $i$ is not the representative of his set, then it can be found by traveling up the tree until we find the representative.

// Finds the representative of the set that i is an element of

public int Find(int i) {

    // If i is the parent of itself

    if (Parent[i] == i) 

        // Then i is the representative of his set

        return i;

}

    else { // Else if i is not the parent of itself

        // Then i is not the representative of his set,

        // so we recursively call Find on its parent

        return Find(Parent[i]);

}

}

The union operation takes, as input, two elements, finds the representatives of their sets using the Find operation, and finally puts either one of the trees (representing the set) under the root node of the other tree, effectively merging the trees and the sets.

public void Union(int i, int j) {

    // Find the representatives (or the root nodes) for the set that includes i

    int irep = this.Find(i),

        // And do the same for the set that includes j

        jrep = this.Find(j);

    // Make the parent of i's representative be j's representative

    // (effectively moving all of i's set into j's set)

    this.Parent[irep] = jrep;

}

 public DisjointSet(int count) {

        this.Count = count;

        this.Parent = new int[this.Count];

        // Initially, all elements are in their own set.

        for (int i = 0; i < this.Count; i++) {

            this.Parent[i] = i;

}

}

The efficiency of disjoint-tree depends heavily on the height of the tree.

Path Compression
This makes the heights of the trees smaller..

public int Find(int i) {

    // If i is the parent of itself

    if (Parent[i] == i) {

        // Then i is the representative of his set

        return i;

}

    else { // Else if i is not the parent of itself

        // Then i is not the representative of his set,

        // so we recursively call Find on it's parent, and save it in our result variable

        int result = Find(Parent[i]);

        // We then cache the result by moving i's node directly under the representative of his set

        Parent[i] = result;

        // And then we return the result

        return result;

}

}

Union by Rank
we need a new array of integers called $\textrm {rank}$ of the same size as the $\textrm {parent}$ array. Then, if $i$ is a representative of a set, $\textrm {rank[}i\textrm{]}$ is the height of the tree representing the set.
If we are uniting two trees (or sets), it's better to put the one with bigger rank under the one with smaller rank.

public void Union(int i, int j) {

    // Find the representatives (or the root nodes) for the set that includes i

    int irep = this.Find(i),

        // And do the same for the set that includes j

        jrep = this.Find(j),

        // Get the rank of i's tree

        irank = Rank[irep],

        // Get the rank of j's tree

        jrank = Rank[jrep];

    // Elements are in the same set, no need to unite anything.

    if (irep == jrep)

        return;

    // If i's rank is less than j's rank

    if (irank < jrank) {

        // Then move i under j

        this.Parent[irep] = jrep;

    } // Else if j's rank is less than i's rank

    else if (jrank < irank) {

        // Then move j under i

        this.Parent[jrep] = irep;

    } // Else if their ranks are the same

    else {

        // Then move i under j (doesn't matter which one goes where)

        this.Parent[irep] = jrep;

        // And increment the the result tree's rank by 1

        Rank[jrep]++;

}

}

http://www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/

// Naive implementation of find

int find(int parent[], int i)

{

    if (parent[i] == -1)

        return i;

    return find(parent, parent[i]);

}

// Naive implementation of union()

void Union(int parent[], int x, int y)

{

    int xset = find(parent, x);

    int yset = find(parent, y);

    parent[xset] = yset;

}

The above union() and find() are naive and the worst case time complexity is linear. The trees created to represent subsets can be skewed and can become like a linked list. Following is an example worst case scenario.

Let there be 4 elements 0, 1, 2, 3

Initially all elements are single element subsets.
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
     2   3   
    /
   1
 /
0

Do Union(2, 3)
         3    
        /
      2
     /
   1
 /
0

The above operations can be optimized to O(Log n) in worst case. The idea is to always attach smaller depth tree under the root of the deeper tree. This technique is called union by rank. The term rank is preferred instead of height because if path compression technique (we have discussed it below) is used, then rank is not always equal to height. Also, size (in place of height) of trees can also be used as rank. Using size as rank also yields worst case time complexity as O(Logn) (See this for prrof)

Let us see the above example with union by rank
Initially all elements are single element subsets.
0 1 2 3 

Do Union(0, 1)
   1   2   3  
  /
 0

Do Union(1, 2)
   1    3
 /  \
0    2

Do Union(2, 3)
    1    
 /  |  \
0   2   3

The second optimization to naive method is Path Compression. The idea is to flatten the tree when find() is called. When find() is called for an element x, root of the tree is returned. The find() operation traverses up from x to find root. The idea of path compression is to make the found root as parent of x so that we don’t have to traverse all intermediate nodes again. If x is root of a subtree, then path (to root) from all nodes under x also compresses.

     
Let the subset {0, 1, .. 9} be represented as below and find() is called
for element 3.
              9
         /    |    \  
        4     5      6
     /     \        /  \
    0        3     7    8
            /  \
           1    2  

When find() is called for 3, we traverse up and find 9 as representative
of this subset. With path compression, we also make 3 as child of 9 so 
that when find() is called next time for 1, 2 or 3, the path to root is 
reduced.

               9
         /    /  \    \
        4    5    6     3 
     /           /  \   /  \
    0           7    8  1   2

The two techniques complement each other. The time complexity of each operations becomes even smaller than O(Logn). In fact, amortized time complexity effectively becomes small constant.

Following is union by rank and path compression based implementation to find cycle in a graph.

// A utility function to find set of an element i

// (uses path compression technique)

int find(struct subset subsets[], int i)

{

    // find root and make root as parent of i (path compression)

    if (subsets[i].parent != i)

        subsets[i].parent = find(subsets, subsets[i].parent);

    return subsets[i].parent;

}

// A function that does union of two sets of x and y

// (uses union by rank)

void Union(struct subset subsets[], int x, int y)

{

    int xroot = find(subsets, x);

    int yroot = find(subsets, y);

    // Attach smaller rank tree under root of high rank tree

    // (Union by Rank)

    if (subsets[xroot].rank < subsets[yroot].rank)

        subsets[xroot].parent = yroot;

    else if (subsets[xroot].rank > subsets[yroot].rank)

        subsets[yroot].parent = xroot;

    // If ranks are same, then make one as root and increment

    // its rank by one

    else

{

        subsets[yroot].parent = xroot;

        subsets[xroot].rank++;

}

}

// The main function to check whether a given graph contains cycle or not

int isCycle( struct Graph* graph )

{

    int V = graph->V;

    int E = graph->E;

    // Allocate memory for creating V sets

    struct subset *subsets =

        (struct subset*) malloc( V * sizeof(struct subset) );

    for (int v = 0; v < V; ++v)

{

        subsets[v].parent = v;

        subsets[v].rank = 0;

}

    // Iterate through all edges of graph, find sets of both

    // vertices of every edge, if sets are same, then there is

    // cycle in graph.

    for(int e = 0; e < E; ++e)

{

        int x = find(subsets, graph->edge[e].src);

        int y = find(subsets, graph->edge[e].dest);

        if (x == y)

            return 1;

        Union(subsets, x, y);

}

    return 0;

}

Read full article from Disjoint-set data structure | MathBlog

Union-Find - Disjoint-set data structure

Labels

Popular Posts