A union-find data structure for maintaining disjoint sets.
npm install union-findunion-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:
``javascript
//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
}
//Label components
var labels = new Array(VERTEX_COUNT)
for(var i=0; i
}
`
Installation
============
`
npm install union-find
`javascript`
var UnionFind = require('union-find')
* numVertices is the number of vertices in the graph
Returns A new union-find data structure
Returns An integer id for the new vertex
Returns An integer id representing the connected component of v
* s and t` are both vertices
Credits
=======
(c) 2013-2014 Mikola Lysenko. MIT License