disjoint

Implementation of a disjoint set.

Supports tracking arbitrary information about each subset and updating it as new links are added.

// Example: 6 elements connected with weighted edges
// Edge weights are in parentheses
// Track maximum edge weight in each subset
//
//    0 -(2)- 1       2
//    |               |
//   (4)             (3)
//    |               |
//    3 -(1)- 4       5
//

const set = new DisjointSet(
  6, // Size of disjoint set
  function(s1, s2, edge) {
    // Reducer for updating subset properties when two subsets are joined.
    // s1: properties of one subset
    // s2: properties of the other subset
    // edge: edge properties, from third argument to union
    return {
      maxWeight: Math.max(s1.maxWeight, s2.maxWeight, edge.weight)
    }
  },
  { maxWeight: 0 } // Initial value for subset properties.
);

// Join elements
set.union(0, 1, { weight: 2 });
set.union(2, 5, { weight: 3 });
set.union(3, 4, { weight: 1 });
set.union(3, 0, { weight: 4 });

// Test if elements are connected
set.isConnected(0, 4); // true
set.isConnected(1, 2); // false

// Number of subsets
set.numSubsets(); // 2

// List of all subsets
set.subsets(); // [ [0, 1, 3, 4], [2, 5] ]

// Subset containing a specific element
set.subset(2) // [2, 5]

// Properties of subset containing a specific element
set.subsetProps(1) // { maxWeight: 4 }

Home

disjoint