- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
LowestCommonAncestorAlgorithm<V>
HeavyPathDecomposition
.
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
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
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate void
Compute the heavy path decomposition and get the corresponding arrays from the internal state.Return the LCA of a and bNote: This operation is not supported.
Return the computed set of LCAs of a and bMethods 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
-
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
-
indexList
-
-
Constructor Details
-
HeavyPathLCAFinder
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
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
-
computeHeavyPathDecomposition
private void computeHeavyPathDecomposition()Compute the heavy path decomposition and get the corresponding arrays from the internal state. -
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
-