Class BinaryLiftingLCAFinder<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    LowestCommonAncestorAlgorithm<V>

    public class BinaryLiftingLCAFinder<V,​E>
    extends java.lang.Object
    implements LowestCommonAncestorAlgorithm<V>
    Algorithm for computing lowest common ancestors in rooted trees and forests using the binary lifting method.

    The method appears in Bender, Michael A., and Martın Farach-Colton. "The level ancestor problem simplified." Theoretical Computer Science 321.1 (2004): 5-12 and it is also nicely presented in the following article on Topcoder for more details about the algorithm.

    Algorithm idea:
    We improve on the naive approach by using jump pointers. These are pointers at a node which reference one of the node’s ancestors. Each node stores jump pointers to ancestors at levels 1, 2, 4, . . . , 2^k.
    Queries are answered by repeatedly jumping from node to node, each time jumping more than half of the remaining levels between the current ancestor and the goal ancestor (i.e. the lca). The worst-case number of jumps is $O(log(|V|))$.

    Preprocessing Time complexity: $O(|V| log(|V|))$
    Preprocessing Space complexity: $O(|V| log(|V|))$
    Query Time complexity: $O(log(|V|))$
    Query Space complexity: $O(1)$

    For small (i.e. less than 100 vertices) trees or forests, all implementations behave similarly. For larger trees/forests with less than 50,000 queries you can use either BinaryLiftingLCAFinder, HeavyPathLCAFinder or EulerTourRMQLCAFinder. Fo more than that use EulerTourRMQLCAFinder since it provides $O(1)$ per query.
    Space-wise, HeavyPathLCAFinder and TarjanLCAFinder only use a linear amount while BinaryLiftingLCAFinder and EulerTourRMQLCAFinder require linearithmic space.
    For DAGs, use NaiveLCAFinder.

    • Field Detail

      • graph

        private final Graph<V,​E> graph
      • roots

        private final java.util.Set<V> roots
      • maxLevel

        private final int maxLevel
      • vertexMap

        private java.util.Map<V,​java.lang.Integer> vertexMap
      • indexList

        private java.util.List<V> indexList
      • ancestors

        private int[][] ancestors
      • timeIn

        private int[] timeIn
      • timeOut

        private int[] timeOut
      • clock

        private int clock
      • numberComponent

        private int numberComponent
      • component

        private int[] component
    • Constructor Detail

      • BinaryLiftingLCAFinder

        public BinaryLiftingLCAFinder​(Graph<V,​E> graph,
                                      V root)
        Construct a new instance of the algorithm.

        Note: The constructor will NOT check if the input graph is a valid tree.

        Parameters:
        graph - the input graph
        root - the root of the graph
      • BinaryLiftingLCAFinder

        public BinaryLiftingLCAFinder​(Graph<V,​E> graph,
                                      java.util.Set<V> roots)
        Construct a new instance of the algorithm.

        Note: If two roots appear in the same tree, an error will be thrown.

        Note: The constructor will NOT check if the input graph is a valid forest.

        Parameters:
        graph - the input graph
        roots - the set of roots of the graph
    • Method Detail

      • normalizeGraph

        private void normalizeGraph()
      • dfs

        private void dfs​(int u,
                         int parent)
      • computeAncestorMatrix

        private void computeAncestorMatrix()
      • isAncestor

        private boolean isAncestor​(int ancestor,
                                   int descendant)
      • getLCA

        public V getLCA​(V a,
                        V b)
        Return the LCA of a and b
        Specified by:
        getLCA in interface LowestCommonAncestorAlgorithm<V>
        Parameters:
        a - the first element to find LCA for
        b - the other element to find the LCA for
        Returns:
        the LCA of a and b, or null if there is no LCA.
      • getLCASet

        public java.util.Set<V> getLCASet​(V a,
                                          V b)
        Note: This operation is not supported.
        Return the computed set of LCAs of a and b
        Specified by:
        getLCASet in interface LowestCommonAncestorAlgorithm<V>
        Parameters:
        a - the first element to find LCA for
        b - the other element to find the LCA for
        Returns:
        the set LCAs of a and b, or empty set if there is no LCA computed.
        Throws:
        java.lang.UnsupportedOperationException - if the method is called