"Is connected?" (Union Find)

union-find.js

/**
 * "Is connected?"
 *
 * Dynamic connectivity issue.
 *
 *    1  2:  not connected
 *    1--2:  connected
 * 1--2--3:  1 and 3 are connected through 2
 *
 * by Dmitry Soshnikov <[email protected]>
 */

/**
 * Solves a connectivity problem, by answering
 * whether two objects are connected in an union.
 */
var UnionFind = {
  /**
   * An array of objects (numbers), where index is an object,
   * and the value is the "component number" to which the
   * object belongs.
   *
   * Definition: two objects are connected if and only if they are
   * in the same component bucket (has the same component number).
   *
   * Initially none of them are connected, since every object
   * in its own component bucket: 0-0, 1-1, etc.
   */
  _data: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],

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

  /**
   * Connects two objects.
   *
   *   1. Move `q` to the same component bucket as `p`.
   *
   *   2. Not only `q`, but every other object that is in the
   *      same component bucket as `q` (to connect them as well).
   *      If 1-2 were connected, and we connect 2 and 3, then
   *      1 and 3 now also should be connected through 2: 1-2-3.
   */
  union: function(p, q) {
    // Current component buckes.
    var pc = this._data[p];
    var qc = this._data[q];
    this._data.forEach(function(c, o) {
      // Move every object from the previous bucket
      // to the new one.
      if (c == pc) {
        this._data[o] = qc;
      }
    }, this);
  },

  /**
   * Returns connected components: a map from component
   * bucket ID to the set of connected components.
   */
  getConnectedComponents: function() {
    var components = {};
    this._data.forEach(function(c, o) {
      (components[c] || (components[c] = [])).push(o);
    });
    return components;
  },

  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

    // {0: [0], 3: [3], 4: [4], 6: [6], 7: [7, 9], 8: [1,2,5,8]}
    console.log(this.getConnectedComponents());
  }
};

UnionFind.runTests();