- 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
.
-
-
Field Summary
Fields Modifier and Type Field Description private int[]
component
private int[]
eulerTour
private Graph<V,E>
graph
private java.util.List<V>
indexList
private int[]
level
private int[]
log2
private int
maxLevel
private int
numberComponent
private int[]
representative
private int[][]
rmq
private java.util.Set<V>
roots
private int
sizeTour
private java.util.Map<V,java.lang.Integer>
vertexMap
-
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 private void
computeAncestorsStructure()
private void
computeRMQ()
private void
dfsIterative(int u, int startLevel)
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 bprivate void
normalizeGraph()
-
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
-
-
-
-
Field Detail
-
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 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
-
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 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
-
-