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 elementsset.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 connectedset.isConnected(0, 4); // trueset.isConnected(1, 2); // false // Number of subsetsset.numSubsets(); // 2 // List of all subsetsset.subsets(); // [ [0, 1, 3, 4], [2, 5] ] // Subset containing a specific elementset.subset(2) // [2, 5] // Properties of subset containing a specific elementset.subsetProps(1) // { maxWeight: 4 }