Union.QuickUnion

union-quick-union.js

/**
 * "Is connected?"
 *
 * Dynamic connectivity issue.
 *
 *    1  2:  not connected
 *    1--2:  connected
 * 1--2--3:  1 and 3 are connected through 2
 *
 * This implements quick union operation, but the find
 * operation can be slow in case of long trees.
 * See also UnionQuickFind: https://gist.github.com/DmitrySoshnikov/3ea31c9bda72304a0f1a
 *
 * by Dmitry Soshnikov <dmitry.soshnikov@gmail.com>
 */

/**
 * Solves a connectivity problem, by answering
 * whether two objects are connected in an union.
 */
var UnionQuickUnion = {
  /**
   * 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],

  _getRoot: function(p) {
    while (p != this._data[p]) {
      p = this._data[p];
    }
    return p;
  },

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

  /**
   * Connects two objects.
   * Change root of p to point to root of q.
   */
  union: function(p, q) {
    var pRoot = this._getRoot(p);
    var qRoot = this._getRoot(q);
    this._data[pRoot] = qRoot;
  },

  runTests: function() {
    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
  }
};

UnionQuickUnion.runTests();