Class EulerTourRMQLCAFinder<V,E>
- java.lang.Object
-
- org.jgrapht.alg.lca.EulerTourRMQLCAFinder<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- 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
orEulerTourRMQLCAFinder
. Fo more than that useEulerTourRMQLCAFinder
since it provides $O(1)$ per query.
Space-wise,HeavyPathLCAFinder
andTarjanLCAFinder
only use a linear amount whileBinaryLiftingLCAFinder
andEulerTourRMQLCAFinder
require linearithmic space.
For DAGs, useNaiveLCAFinder
.- Author:
- Alexandru Valeanu
-
-
Constructor Summary
Constructors Constructor Description EulerTourRMQLCAFinder(Graph<V,E> graph, java.util.Set<V> roots)
Construct a new instance of the algorithm.EulerTourRMQLCAFinder(Graph<V,E> graph, V root)
Construct a new instance of the algorithm.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description V
getLCA(V a, V b)
Return the LCA of a and bjava.util.Set<V>
getLCASet(V a, V b)
Note: This operation is not supported.
Return the computed set of LCAs of a and b-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface org.jgrapht.alg.interfaces.LowestCommonAncestorAlgorithm
getBatchLCA, getBatchLCASet
-
-
-
-
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 graphroot
- 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 graphroots
- 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 interfaceLowestCommonAncestorAlgorithm<V>
- Parameters:
a
- the first element to find LCA forb
- 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 interfaceLowestCommonAncestorAlgorithm<V>
- Parameters:
a
- the first element to find LCA forb
- 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
-
-