- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
LowestCommonAncestorAlgorithm<V>
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 Summary
FieldsModifier and TypeFieldDescriptionprivate int[]
private int[]
private int[]
private int[]
private final int
private int
private int[]
private int[][]
private int
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate void
private void
private void
dfsIterative
(int u, int startLevel) Return the LCA of a and bNote: This operation is not supported.
Return the computed set of LCAs of a and bprivate void
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 Details
-
graph
-
roots
-
maxLevel
private final int maxLevel -
vertexMap
-
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
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
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 Details
-
normalizeGraph
private void normalizeGraph() -
dfsIterative
private void dfsIterative(int u, int startLevel) -
computeRMQ
private void computeRMQ() -
computeAncestorsStructure
private void computeAncestorsStructure() -
getLCA
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
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:
UnsupportedOperationException
- if the method is called
-