disjoint set stuff

gistfile1.js

// return the root of the tree, this is a static representative of the
// set that a node belongs to
function find(node) {
  // track which nodes are on the path to the root, hang them off the
  // root if they aren't already
  var path = []
  while (node.parent !== node) {
    if (node.parent.parent !== node.parent) path.push(node)
    node = node.parent
  }
  path.forEach(function (n) {
    n.parent = node
  })
  return node
}

// union two sets by representative elements (e.g. having {1,2}, {3,4},
// union (1,4) will create {1,2,3,4}
function union (first, second) {
  // find a representative for both sets
  var firstRoot = find(first)
  var secondRoot = find(second)
  // if the representatives are the same, don't do anything
  if (firstRoot === secondRoot) return
  // if they are different join the sets by hanging one off the other
  firstRoot.parent = secondRoot
}

// interface is anything with a parent field
function Node(value) {
  this.value = value
  this.parent = this
}

// start test code
nodes = []
for (var i = 0; i < 10; i++) {
  nodes.push(new Node(i))
}

union(nodes[0], nodes[1])
union(nodes[2], nodes[3])
union(nodes[4], nodes[5])
union(nodes[6], nodes[7])
union(nodes[8], nodes[9])
union(nodes[0], nodes[7])
union(nodes[0], nodes[9])
union(nodes[0], nodes[2])
union(nodes[0], nodes[4])

for (var i = 0; i < nodes.length; i++){
  console.log('Node ' + nodes[i].value + ' has a depth of ' + getDepth(nodes[i]))
}

displayNodes(nodes)

function displayNodes(nodes) {
  var roots = {}

  nodes.forEach(function (node) {
    var root = find(node)
    if (roots[root.value] === undefined) roots[root.value] = []
    roots[root.value].push(node.value)
  })

  console.log('{')
  for (root in roots) {
    console.log('[' + roots[root] + '],')
  }
  console.log('}')
}

function findDepth(node, currentDepth) {
  if (node.parent === node) return currentDepth
  return findDepth(node.parent, currentDepth + 1)
}

function getDepth(node) {
  return findDepth(node, 0)
}