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 structurevar UnionFind = var VERTEX_COUNT = 8var edges = 01 12 23 56 71 //Link all the nodes togethervar forest = VERTEX_COUNTforvar i=0; i<edgeslength; ++i forestlinkedgesi0 edgesi1 //Label componentsvar labels = VERTEX_COUNTforvar i=0; i<VERTEX_COUNT; ++i labelsi = forest
Installation
npm install union-find
API
var UnionFind =
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
andt
are both vertices
Credits
(c) 2013-2014 Mikola Lysenko. MIT License