Union.QuickUnion.Weight

union-quick-union-weight.js

/**
 * "Is connected?"
 *
 * Dynamic connectivity issue.
 *
 *    1  2:  not connected
 *    1--2:  connected
 * 1--2--3:  1 and 3 are connected through 2
 *
 * This implementation uses concept of a "weight" to avoid too long trees:
 * this is an optimization for search. Weighting algorithm keeps track of a
 * "rank" (weight, which is a number of objects in the tree), and always
 * attaches root of a smaller tree to the root of a larger tree.
 *
 * See also:
 *
 *   - Quick find: https://gist.github.com/DmitrySoshnikov/3ea31c9bda72304a0f1a
 *
 *   - Quick union: https://gist.github.com/DmitrySoshnikov/4ca0628cc0901bf3a49c
 *     (tree but with no raking optimization)
 *
 * by Dmitry Soshnikov <[email protected]>
 */

'use strict';

/**
 * Solves a connectivity problem, by answering
 * whether two objects are connected in an union.
 */
let UnionQuickUnionRank = {
  /**
   * An array of objects (numbers), where index is an object,
   * and the value is the parent node in the tree representation
   * of the connected components.
   *
   * Definition: two objects are connected if and only if they are
   * in the same component bucket (has the same root in the tree).
   *
   * Initially none of them are connected, since every object
   * is the root node: 0-0, 1-1, etc.
   */
  _data: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],

  /**
   * Ranking array: keeps sizes of each tree. Initially all
   * trees have size 1, since only one element in a tree.
   */
  _sizes: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],

  _getRoot(p) {
    while (p != this._data[p]) {

      // Path compression optimization. We re-attach deeper trees to upper
      // nodes belonging to this root.
      this._data[p] = this._data[this._data[p]];

      p = this._data[p];
    }
    return p;
  },

  /**
   * Checks whether two objects are connected.
   */
  connected(p, q) {
    return this._getRoot(p) == this._getRoot(q);
  },

  /**
   * Connects two objects.
   * Change root of p to point to root of q.
   */
  union(p, q) {
    let pRoot = this._getRoot(p);
    let qRoot = this._getRoot(q);

    if (pRoot === qRoot) {
      return;
    }

    if (this._sizes[pRoot] < this._sizes[qRoot]) {
      this._data[pRoot] = qRoot;
      this._sizes[qRoot] += this._sizes[pRoot];
    } else {
      this._data[qRoot] = pRoot;
      this._sizes[pRoot] += this._sizes[qRoot];
    }
  },

  runTests() {
    console.log(this.connected(1, 2)); // false
    this.union(1, 2); // 1-2
    console.log(this.connected(1, 2)); // true

    this.union(2, 5);
    console.log(
      this.connected(2, 5), // true
      this.connected(1, 5) // true, via 1-2-5
    );

    this.union(1, 8);
    console.log(this.connected(5, 8)); // true: 1-8 -> 1-5 -> 5-8

    this.union(9, 7);
    console.log(this.connected(7, 9)); // true: 9-7 -> 7-9
  }
};

UnionQuickUnionRank.runTests();