Module org.jgrapht.core
Package org.jgrapht.alg.lca

Class EulerTourRMQLCAFinder<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    LowestCommonAncestorAlgorithm<V>
    public class EulerTourRMQLCAFinder<V,​E>
extends java.lang.Object
implements LowestCommonAncestorAlgorithm<V>
    Algorithm for computing lowest common ancestors in rooted trees and forests based on Berkman, Omer; Vishkin, Uzi (1993), "Recursive Star-Tree Parallel Data Structure", SIAM Journal on Computing, 22 (2): 221–242, doi:10.1137/0222017.

    The algorithm involves forming an Euler tour of a graph formed from the input tree by doubling every edge, and using this tour to compute a sequence of level numbers of the nodes in the order the tour visits them. A lowest common ancestor query can then be transformed into a query that seeks the minimum value occurring within some subinterval of this sequence of numbers.

    Preprocessing Time complexity: $O(|V| log(|V|))$
    Preprocessing Space complexity: $O(|V| log(|V|))$
    Query Time complexity: $O(1)$
    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

      • eulerTour

        private int[] eulerTour

      • sizeTour

        private int sizeTour

      • numberComponent

        private int numberComponent

      • component

        private int[] component

      • level

        private int[] level

      • representative

        private int[] representative

      • rmq

        private int[][] rmq

      • log2

        private int[] log2

    • Constructor Detail

      • EulerTourRMQLCAFinder

        public EulerTourRMQLCAFinder​(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

      • EulerTourRMQLCAFinder

        public EulerTourRMQLCAFinder​(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()

      • dfsIterative

        private void dfsIterative​(int u,
                          int startLevel)

      • computeRMQ

        private void computeRMQ()

      • computeAncestorsStructure

        private void computeAncestorsStructure()

      • 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