union-find

A basic union-find data structure for node.js. For more information, see wikipdia:

Union find data structures solve the incremental connectivity problem. (That is maintaining a spanning forest under incremental insertions of edges.) To handle fully dynamic connectivity, you can use a dynamic forest data structure.

Usage

Here is an example showing how to do connected component labelling. Assume we are given a graph with VERTEX_COUNT vertices and a list of edges stored in array represented by pairs of vertex indices:

//Import data structure
var UnionFind = require('union-find')

var VERTEX_COUNT = 8
var edges = [
    [0,1],
    [1,2],
    [2,3],
    [5,6],
    [7,1]
]

//Link all the nodes together
var forest = new UnionFind(VERTEX_COUNT)
for(var i=0; i<edges.length; ++i) {
  forest.link(edges[i][0], edges[i][1])
}

//Label components
var labels = new Array(VERTEX_COUNT)
for(var i=0; i<VERTEX_COUNT; ++i) {
  labels[i] = forest.find(i)
}

Installation

npm install union-find

API

var UnionFind = require('union-find')

Constructor

`var forest = new UnionFind(numVertices)`

Creates a new union-find data structure.

numVertices is the number of vertices in the graph

Returns A new union-find data structure

Methods

`forest.length`

Returns the number of vertices in the forest

`forest.makeSet()`

Creates a new vertex

Returns An integer id for the new vertex

`forest.find(v)`

Returns an identifier representing the connected component of any given vertex

Returns An integer id representing the connected component of v

`forest.link(s, t)`

Links a pair of connected components together

s and t are both vertices

Credits

Current Tags

1.0.2 ... latest (11 years ago)

2 Versions

0.0.4 ... 13 years ago
1.0.2 ... 11 years ago