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