Sign Up for Free

RunKit +

Try any Node.js package right in your browser

This is a playground to test code. It runs a full Node.js environment and already has all of npm’s 400,000 packages pre-installed, including dynamic-forest with all npm packages installed. Try it out:

var dynamicForest = require("dynamic-forest")

This service is provided by RunKit and is not affiliated with npm, Inc or the package authors.

dynamic-forest v1.0.0

Maintains connectivity information for a graph under dynamic insertions and deletions


Maintains a spanning forest for an arbitrary undirected graph under incremental edge insertions and deletions. Implementation based on the following algorithm:

J. Holm, K. de Lichtenberg and M. Thorrup. "Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge connectivity and biconnectivity". 2001. Journal of the ACM

Connectivity queries can be answered in O(log(size of component)), and updates take O(log(number of vertices)^2) time. The total space complexity is O((number of edges + number of vertices) * log(number of vertices)).

This code works both in node.js and in the browser using browserify.


//Load the module
var createVertex = require("dynamic-forest")

//Create some vertices
var a = createVertex("a")
var b = createVertex("b")
var c = createVertex("c")
var d = createVertex("d")

//Print out connectivity between a and c
console.log(a.connected(c))   //Prints out "false"

//Link vertices together in a cycle
var ab =
var bc =
var cd =
var da =

//Vertices are now connected
console.log(a.connected(c))     //Prints out "true"

//Cut the edge between b and c

//Still connected
console.log(a.connected(c))    //Prints "true"

//Cut edge between a and d

//Finally a and c are disconnected
console.log(a.connected(c))   //Prints "false"


npm install dynamic-forest


var createVertex = require("dynamic-forest")


var vertex = createVertex([value])

Creates a vertex

  • value is an optional user specified value that is stored with the vertex

Returns A new vertex object


The user specified value associated to this vertex


An array of all the edges incident to this vertex

var edge =[, value])

Creates an edge linking vertex to other in the graph.

  • other the vertex to link to
  • value is an optional user specified value for the edge

Returns A new edge linking vertex to other

Complexity O(log(number of vertices)), but amortized O(log(number of vertices)^2)


Check if two vertices are connected by a path

  • other is the other vertex to check

Complexity O(log(size of component))

Returns true if there is a path connecting vertex to other within the graph


Disconnects the vertex from the rest of the graph


Number of vertices in the connected component containing this vertex

var iterator = vertex.component()

Returns an iterator for the connected component containing the vertex



The first vertex of the edge


The second vertex of the edge


The user-specified value associated with the edge


Removes the edge from the graph

Time Complexity O(log(number of vertices)^2) amortized

Component Iterator

The component iterator object supports fast traversal of connected components within the graph.


Returns the vertex at the position of the iteroator


Returns the number of vertices in the connected component


Returns true if the iterator is valid or not

Advances the iterator to the next position


Returns true if iterator has a successor


Moves iterator back one vertex


Returns true if iterator has a predecessor


Move iterator to first vertex in component


Advance iterator to last vertex in component


(c) 2013 Mikola Lysenko. MIT License

RunKit is a free, in-browser JavaScript dev environment for prototyping Node.js code, with every npm package installed. Sign up to share your code.
Sign Up for Free