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

Class TarjanLCAFinder<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    LowestCommonAncestorAlgorithm<V>
    public class TarjanLCAFinder<V,​E>
extends java.lang.Object
implements LowestCommonAncestorAlgorithm<V>
    Tarjan's offline algorithm for computing lowest common ancestors in rooted trees and forests.

    See the article on wikipedia for more information on the algorithm.

    The original algorithm can be found in Gabow, H. N.; Tarjan, R. E. (1983), "A linear-time algorithm for a special case of disjoint set union", Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 246–251, doi:10.1145/800061.808753

    Preprocessing Time complexity: $O(1)$
    Preprocessing Space complexity: $O(1)$
    Query Time complexity: $O(|V| log^{*}(|V|) + |Q|)$ where $|Q|$ is the number of queries
    Query Space complexity: $O(|V| + |Q|)$ where $|Q|$ is the number of queries

    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 Graph<V,​E> graph

      • roots

        private java.util.Set<V> roots

      • ancestors

        private java.util.Map<V,​V> ancestors

      • blackNodes

        private java.util.Set<V> blackNodes

      • queryOccurs

        private java.util.HashMap<V,​java.util.Set<java.lang.Integer>> queryOccurs

      • lowestCommonAncestors

        private java.util.List<V> lowestCommonAncestors

      • queries

        private java.util.List<Pair<V,​V>> queries

    • Constructor Detail

      • TarjanLCAFinder

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

      • TarjanLCAFinder

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

      • 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.

      • getBatchLCA

        public java.util.List<V> getBatchLCA​(java.util.List<Pair<V,​V>> queries)
        Return a list of LCAs for a batch of queries
        Specified by:
        getBatchLCA in interface LowestCommonAncestorAlgorithm<V>
        Parameters:
        queries - a list of pairs of vertices
        Returns:
        a list L of LCAs where L(i) is the LCA for pair queries(i)

      • initialize

        private void initialize()

      • clear

        private void clear()

      • computeTarjan

        private java.util.List<V> computeTarjan​(java.util.List<Pair<V,​V>> queries)

      • computeTarjanOLCA

        private void computeTarjanOLCA​(V u,
                               V p,
                               java.util.Set<V> visited)

      • 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