Package com.jgalgo.alg.tree

Class LowestCommonAncestorDynamicGabowLongs

java.lang.Object

com.jgalgo.alg.tree.LowestCommonAncestorDynamicGabowLongs

All Implemented Interfaces:

LowestCommonAncestorDynamic

public class LowestCommonAncestorDynamicGabowLongs
extends Object
implements LowestCommonAncestorDynamic

Gabow linear dynamic LCA data structure with 64bit word operations.

The algorithm use LowestCommonAncestorDynamicGabowSimple as a base, but uses two layers of bit tricks to remove the \(O(\log^2 n)\) factor of the simpler data structure. Each layer have less vertices than the previous one by a factor of \(O(\log n)\), until the simpler data structure is used on \(O(n / \log^2 n)\) vertices. This implementation is much faster in practice and always should be used over the simpler one.

The running time of this algorithm for \(m\) operations is \(O(n + m)\) and it uses linear space. More specifically, the addLeaf(LowestCommonAncestorDynamic.Vertex) operation is perform in \(O(1)\) amortized time and findLowestCommonAncestor(LowestCommonAncestorDynamic.Vertex, LowestCommonAncestorDynamic.Vertex) is perform in constant time.

This class implements all the bit operations on long primitive. For a version that uses int see LowestCommonAncestorDynamicGabowInts, which usually perform worse, but may perform better for (significantly) smaller graphs.

Based on 'Data Structures for Weighted Matching and Nearest Common Ancestors with Linking' by Harold N. Gabow (1990).

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.tree.LowestCommonAncestorDynamic

LowestCommonAncestorDynamic.Vertex

Constructor Summary

Constructors

Constructor	Description
LowestCommonAncestorDynamicGabowLongs()	Create a new dynamic LCA data structure that contains zero vertices.

Method Summary

Modifier and Type	Method	Description
LowestCommonAncestorDynamic.Vertex	addLeaf(LowestCommonAncestorDynamic.Vertex parent)	Add a new leaf vertex to the tree.
void	clear()	Clear the data structure by removing all vertices in the tree.
LowestCommonAncestorDynamic.Vertex	findLowestCommonAncestor(LowestCommonAncestorDynamic.Vertex x, LowestCommonAncestorDynamic.Vertex y)	Find the lowest common ancestor of two vertices in the tree.
LowestCommonAncestorDynamic.Vertex	initTree()	Initialize the tree the LCA will operate on and create a root vertex.
int	size()	Get the number of vertices in the tree.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

LowestCommonAncestorDynamicGabowLongs

public LowestCommonAncestorDynamicGabowLongs()

Create a new dynamic LCA data structure that contains zero vertices.

Please prefer using LowestCommonAncestorDynamic.newInstance() to get a default implementation for the LowestCommonAncestorDynamic interface.

Method Detail

initTree

public LowestCommonAncestorDynamic.Vertex initTree()

Description copied from interface: LowestCommonAncestorDynamic

Initialize the tree the LCA will operate on and create a root vertex.

Specified by:

initTree in interface LowestCommonAncestorDynamic

Returns:

the new root vertex

addLeaf

public LowestCommonAncestorDynamic.Vertex addLeaf(LowestCommonAncestorDynamic.Vertex parent)

Description copied from interface: LowestCommonAncestorDynamic

Add a new leaf vertex to the tree.

Specified by:

addLeaf in interface LowestCommonAncestorDynamic

Parameters:

parent - parent of the new vertex

Returns:

the new vertex

findLowestCommonAncestor

public LowestCommonAncestorDynamic.Vertex findLowestCommonAncestor(LowestCommonAncestorDynamic.Vertex x,
                                                                   LowestCommonAncestorDynamic.Vertex y)

Description copied from interface: LowestCommonAncestorDynamic

Find the lowest common ancestor of two vertices in the tree.

Specified by:

findLowestCommonAncestor in interface LowestCommonAncestorDynamic

Parameters:

x - the first vertex

y - the second vertex

Returns:

the lowest common ancestor of the two vertices

size

public int size()

Description copied from interface: LowestCommonAncestorDynamic

Get the number of vertices in the tree.

Specified by:

size in interface LowestCommonAncestorDynamic

Returns:

number of vertices in the tree

clear

public void clear()

Description copied from interface: LowestCommonAncestorDynamic

Clear the data structure by removing all vertices in the tree.

Specified by:

clear in interface LowestCommonAncestorDynamic