Package com.jgalgo.alg.tree

Class LowestCommonAncestorDynamicGabowSimple

java.lang.Object

com.jgalgo.alg.tree.LowestCommonAncestorDynamicGabowSimple

All Implemented Interfaces:

LowestCommonAncestorDynamic

public class LowestCommonAncestorDynamicGabowSimple
extends Object
implements LowestCommonAncestorDynamic

Gabow implementation for dynamic LCA data structure with \(O(\log^2 n)\) amortized time for addLeaf() operation.

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

This implementation is used by the better linear LCA algorithm LowestCommonAncestorDynamicGabowInts and LowestCommonAncestorDynamicGabowLongs and rarely should be used directly.

Based on the simpler data structure presented in '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
LowestCommonAncestorDynamicGabowSimple()	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

LowestCommonAncestorDynamicGabowSimple

public LowestCommonAncestorDynamicGabowSimple()

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