merge-find v0.3.5
merge-find
Implementation of Disjoint-set data structure algorithm (also called a union–find data structure or merge–find set) with TypeScript support.
Hit the Star button if you love this project ⭐️
📝 Disjoint-set data structure algorithm
In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation makes it possible to find out efficiently if any two elements are in the same or different sets.
🚀 Installation
NPM
npm install merge-findYarn
yarn add merge-find👩💻 Usage
import {DisjointSet} from 'merge-find'
type MyNodeType = {
name: string
}
// instantiate disjoint-set data structure
const disjointSet = new DisjointSet<MyNodeType>()
// add nodes to the set
const id1 = disjointSet.add({
name: 'First node'
}) // 0
const id2 = disjointSet.add({
name: 'Second node'
}) // 1
const id3 = disjointSet.add({
name: 'Third node'
}) // 2
// Merge some nodes together
disjointSet.union(0, 1)
// Check if nodes are connected
disjointSet.areConnected(0, 1); // true
disjointSet.areConnected(0, 2); // false
// Number of subsets
disjointSet.numberOfSubsets(); // 2
// List of all subsets
disjointSet.subsets();
/* [ [ { id: 0, parent: -1, rank: 1, name: 'First node' },
{ id: 1, parent: 0, rank: 0, name: 'Second node' } ],
[ { id: 2, parent: -1, rank: 0, name: 'Third node' } ] ] */
// Subset containing a specific node
disjointSet.subset(2) // [ { id: 2, parent: -1, rank: 0, name: 'Third node' } ]You can try it live on replit.
🌐 API
Creation
| Factory | Description |
|---|---|
| new DisjointSet<T>() | Instantiates disjoint-set data structure. |
Methods
Types
The DisjointSetNodeType<T> type is:
type DisjointSetNodeType<T> = T & {
id: number
parent: number
rank: number
}