Nuclear Pumpkin Mocha

## dynamic-forest

1.0.0 • Public • Published

# dynamic-forest

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.

# API

## Vertices

### 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

### vertex.valueOf()

The user specified value associated to this vertex

An array of all the edges incident to this vertex

### var edge = vertex.link(other[, 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)

### vertex.connected(other)

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

### vertex.cut()

Disconnects the vertex from the rest of the graph

### vertex.componentSize()

Number of vertices in the connected component containing this vertex

### var iterator = vertex.component()

Returns an iterator for the connected component containing the vertex

## Edges

### edge.s

The first vertex of the edge

### edge.t

The second vertex of the edge

### edge.valueOf()

The user-specified value associated with the edge

### edge.cut()

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.

### iterator.vertex()

Returns the vertex at the position of the iteroator

### iterator.size()

Returns the number of vertices in the connected component

### iterator.valid()

Returns true if the iterator is valid or not

### iterator.next()

Advances the iterator to the next position

### iterator.hasNext()

Returns true if iterator has a successor

### iterator.prev()

Moves iterator back one vertex

### iterator.hasPrev()

Returns true if iterator has a predecessor

### iterator.first()

Move iterator to first vertex in component

### iterator.last()

Advance iterator to last vertex in component

# Credits

(c) 2013 Mikola Lysenko. MIT License

## Keywords

### install

npm i dynamic-forest

2

1.0.0

MIT

github