Package com.jgalgo.alg.tree

Class LowestCommonAncestorDynamicGabowInts

java.lang.Object
com.jgalgo.alg.tree.LowestCommonAncestorDynamicGabowInts
All Implemented Interfaces:
LowestCommonAncestorDynamic
public class LowestCommonAncestorDynamicGabowInts extends Object implements LowestCommonAncestorDynamic
Gabow linear dynamic LCA data structure with 32bit 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 int primitive. For a version that uses long see LowestCommonAncestorDynamicGabowLongs, which usually perform better, especially for larger graphs.

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

Author:
Barak Ugav