Union Find Model Algorithms

A Union Find Model Algorithm is used to return if a node is connected to another through a path.

Example of a connected structure

• Set of N Objects
• Connection between two objects - UNION COMMAND
• Find if there’s a path connecting the two objects. (regardless of how many nodes are connected between) - CONNECTED, UNION FIND COMMAND

Applications of Union Find Models

• Pixels in digital media
• Networking
• Transistors in Chips
• Mathematical sets
• Variable Names in Fortran programs (????????What?????) <— Go look into this.

Modelling Connections and Definitions

Assume “is connected to” is an equivalence relation:

• Reflexive: p is connected to p. (Reflexive means referring to oneself using a pronoun e.g. Myself)
• Symmetric: if p is connected to q then q is connected to p.
• Transitive: if p is connected to q is connected to r, then p is connected to r.

Connected Components: Connected components are a maximal set of objects that are mutually connected.

Operations

Find Query: Check if two objects are in the same component. Union Command: Replace components containing two objects with their union.

Union-Find Data Type (API)

In Java typically we would design a class called UF with two methods one for union and one for connected (Boolean return). Constructor takes number of objects as an argument.

Quick Union-Find (Eager)

class UF {
    constructor(n) {
        this.id = []
        for (let i = 0; i < n; i++) {
            this.id[i] = i
        }
    }

    connected(p, q) {
        return this.id[p] == this.id[q]
    }

    union(p, q) {
        const pid = this.id[p]
        const qid = this.id[q]
        for (let i = 0; i < this.id.length; i++) {
            if (this.id[i] == pid) {
                this.id[i] = qid
            }
        }
    }
}

const test = new UF(10)
console.log(test.id)
test.union(1, 4)
console.log(test.connected(1, 4))

The Quick Find Union option is expensive due to the number of times the code needs to access the array to initialise and create unions which both go through the entire array as an example N union on N objects would take quadratic time (squared time) - Quadratic time is much to slow for large problems

Quadratic algorithms don’t scale and get slower as our sets grow.

Quick Union-Find (Lazy)

Same data structure different interpretation. In this approach we are taking a tree structure in which we also store the parent of each entry.

JS implementation of Quick Union for this approach:

// Quick Union Find
class UF {
    constructor(n) {
        this.id = []
        for (let i = 0; i < n; i++) {
            this.id[i] = i
        }
    }

    #root(i) {
        while (i != this.id[i]) i = this.id[i]
        return i
    }

    connected(p, q) {
        return this.#root(p) == this.#root(q)
    }

    union(p, q) {
        const i = this.#root(p)
        const j = this.#root(q)
        this.id[i] = j
    }
}

const test = new UF(10)
console.log(test.connected(1, 3))
test.union(1, 3)
console.log(test.connected(1, 3))

Quick Union can also be an expensive operation as our Trees can get too tall creating an expensive find operation with our root loops taking N time. The growth in operational requirement in Quick Union is Linear in nature.

Weighted Quick-Union

As both Quick Find and Quick Union on their own are not optimised and can cause memory heavy operations to occur we need to start improving our algorithm.

The first approach might be to apply weighting.

• We first modify the union to have bounds associated with our trees.
• Need to Keep track of our tree sizes.
• Ensure our UNION operations take into account which node is in the bigger tree and which node is in the smaller tree moving smaller trees to bigger trees.
• Should the tree sizes be equal tree’s simply merge.

A weighted quick union algorithm always ensures the smaller tree goes below.

Immediate Improvements

As a weighted quick union helps flatten our structure and reduces the distance between nodes we see an immediate reduction of up to on average 3x in distance between nodes resulting in significant improvements for both find and union operations.

Implementation

Data Structure

• As per our initial implementations we will us an array which takes its position as node and value as connected.
• We will also now need to take into account an extra array to count the number of objects in the tree rooted at i

  constructor(n) {
    this.id = [];
    this.sz = [];
    for (let i = 0; i < n; i++) {
      this.id[i] = i;
      this.sz[i] = i;
    }
  }

Find

• The find function remains the same using the private root class

  #root(i) {
    while (i != this.id[i]) i = this.id[i];
    return i;
  }

  connected(p, q) {
    return this.#root(p) == this.#root(q);
  }

Union

• We are going to modify the union implementation to check the sizes of each connected component linking the root of our smaller tree to the root of our larger tree.

  union(p, q) {
    const i = this.#root(p);
    const j = this.#root(q);
    if (i == j) return;
    if (this.sz[i] < this.sz[j]) {
      this.id[i] = j;
      this.sz[j] += this.sz[i];
    } else {
      this.id[j] = i;
      this.sz[i] += this.sz[j];
    }
  }
}

Updated Code In Full

// WEIGHTED QUICK UNION
class UF {
    constructor(n) {
        this.id = []
        this.sz = []
        for (let i = 0; i < n; i++) {
            this.id[i] = i
            this.sz[i] = i
        }
    }

    #root(i) {
        while (i != this.id[i]) i = this.id[i]
        return i
    }

    connected(p, q) {
        return this.#root(p) == this.#root(q)
    }

    union(p, q) {
        const i = this.#root(p)
        const j = this.#root(q)
        if (i == j) return
        if (this.sz[i] < this.sz[j]) {
            this.id[i] = j
            this.sz[j] += this.sz[i]
        } else {
            this.id[j] = i
            this.sz[i] += this.sz[j]
        }
    }
}

const test = new UF(10)
console.log(test.connected(1, 3))
test.union(1, 3)
console.log(test.connected(1, 3))

Mathematical Performance Improvements

• Find: Takes time proportional to the depth of p and q
• Union: Takes constant time, given roots.

Depth of any node x is at most lg (Base 2 Logarithm) n

$N = 1000 x = 10$ $N = 1000000 x = 20$ $N = 1B x = 30$

Proof of improvement

We can further optimise the Weighted Quick Union by adding compression to the algorithm. The concept is simple, as we loop through each node we update the root of those nodes further compressing our connected component tree structure reducing computing requirements in future FIND operations.

To modify the operation we add one line of code!

  #root(i) {
    while (i != this.id[i]) {
      this.id[i] = this.id[this.id[i]];
      i = this.id[i];
    }
    return i;
  }

Side Note: See Here for how applications spark some amazing math propositions.

Extra reading material: Iterated Logarithm Ackermann Function