Class EulerTourRMQLCAFinder<V,E>

java.lang.Object
org.jgrapht.alg.lca.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 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 Details

    • graph

      private final Graph<V,E> graph

    • roots

      private final Set<V> roots

    • maxLevel

      private final int maxLevel

    • vertexMap

      private Map<V,Integer> vertexMap

    • indexList

      private 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 Details

    • 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, 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 Details

    • 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 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:
      UnsupportedOperationException - if the method is called