- java.lang.Object
-
- org.jgrapht.alg.lca.HeavyPathLCAFinder<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
LowestCommonAncestorAlgorithm<V>
public class HeavyPathLCAFinder<V,E> extends java.lang.Object implements LowestCommonAncestorAlgorithm<V>
Algorithm for computing lowest common ancestors in rooted trees and forests based onHeavyPathDecomposition
.Preprocessing Time complexity: $O(|V|)$
Preprocessing Space complexity: $O(|V|)$
Query Time complexity: $O(log(|V|))$
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[]
depth
private int[]
firstNodeInPath
private Graph<V,E>
graph
private java.util.List<V>
indexList
private int[]
parent
private int[]
path
private int[]
positionInPath
private java.util.Set<V>
roots
private java.util.Map<V,java.lang.Integer>
vertexMap
-
Constructor Summary
Constructors Constructor Description HeavyPathLCAFinder(Graph<V,E> graph, java.util.Set<V> roots)
Construct a new instance of the algorithm.HeavyPathLCAFinder(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
computeHeavyPathDecomposition()
Compute the heavy path decomposition and get the corresponding arrays from the internal state.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
-
-
-
-
Field Detail
-
roots
private final java.util.Set<V> roots
-
parent
private int[] parent
-
depth
private int[] depth
-
path
private int[] path
-
positionInPath
private int[] positionInPath
-
component
private int[] component
-
firstNodeInPath
private int[] firstNodeInPath
-
vertexMap
private java.util.Map<V,java.lang.Integer> vertexMap
-
indexList
private java.util.List<V> indexList
-
-
Constructor Detail
-
HeavyPathLCAFinder
public HeavyPathLCAFinder(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
-
HeavyPathLCAFinder
public HeavyPathLCAFinder(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
-
computeHeavyPathDecomposition
private void computeHeavyPathDecomposition()
Compute the heavy path decomposition and get the corresponding arrays from the internal state.
-
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
-
-