union-find-ts
v1.0.9
Published
An immutable Union-Find structure.
Downloads
12
Readme
union-find-ts
[![npm package][npm-img]][npm-url] [![Build Status][build-img]][build-url] [![Downloads][downloads-img]][downloads-url] [![Issues][issues-img]][issues-url] [![Code Coverage][codecov-img]][codecov-url]
An immutable Union-Find structure.
The main purpose of this structure is to simplify the search algorithm for finding paths that join two previously disconnected components.
Not suitable for large data sets, since find()
does not compress paths in-place and because
in order to achieve immutability, each link
operation copies the data structure.
Install
npm install union-find-ts
Usage
const gates = [
20, 34, 63, 64, 55, 24, 53, 20, 17, 6, 52, 57, 7, 59, 55, 37, 40, 52, 40, 64, 31, 21, 46, 39,
57, 4
]
const gatesByCenter = groupBy(item => item.center.toString(), allItems)
const gateNumbers: Set<number> = new Set(gates)
const defined = gateNumbers.has.bind(gateNumbers)
const uf = unionFind(
allItems,
gateNum,
/**
* This is where we define which gates each one is connected to.
* Each gate is connected to the other items on its center,
* as well as the channel connection.
* @param param0
* @returns
*/
({ item: gate }) =>
!defined(gate.num)
? []
: [...gate.connected, ...gatesByCenter[gate.center.toString()].map(gateNum)].filter(
defined
)
)
const groups = toConnectedGroups(uf)
expect(groups.length).toBe(2)
const findItemArray = lift(findItemByNum)
function candidates(item: TestInterface): TestInterface[] {
return concat(findItemArray(item.connected), gatesByCenter[item.center.toString()])
}
const solution = findPath(uf, candidates, groups[1][0], groups[0][0])
const result = [[allItems.find(it => it.num === 62)]]
expect(solution.isJust()).toBeTruthy()
expect(solution.extract()).toEqual(result)
Credits
This is a rewrite of Union Find.