## Interface LowestCommonAncestorAlgorithm<V>

• Type Parameters:
V - vertex the graph vertex type
All Known Implementing Classes:
BinaryLiftingLCAFinder, EulerTourRMQLCAFinder, HeavyPathLCAFinder, NaiveLCAFinder, TarjanLCAFinder

public interface LowestCommonAncestorAlgorithm<V>
Algorithm to compute a lowest common ancestor in a tree, forest or DAG.
Author:
Alexandru Valeanu
• ### Method Summary

All Methods
Modifier and Type Method Description
default List<V> getBatchLCA​(List<Pair<V,​V>> queries)
Return a list of LCAs for a batch of queries
default List<Set<V>> getBatchLCASet​(List<Pair<V,​V>> queries)
Return a list of computed sets of LCAs for a batch of queries
V getLCA​(V a, V b)
Return the LCA of a and b
Set<V> getLCASet​(V a, V b)
Return the computed set of LCAs of a and b
• ### Method Detail

• #### getLCA

V getLCA​(V a,
V b)
Return the LCA of a and b
Parameters:
a - the first element to find LCA for
b - the other element to find the LCA for
Returns:
the LCA of a and b, or null if there is no LCA.
• #### getBatchLCA

default List<V> getBatchLCA​(List<Pair<V,​V>> queries)
Return a list of LCAs for a batch of queries
Parameters:
queries - a list of pairs of vertices
Returns:
a list L of LCAs where L(i) is the LCA for pair queries(i)
• #### getLCASet

Set<V> getLCASet​(V a,
V b)
Return the computed set of LCAs of a and b
Parameters:
a - the first element to find LCA for
b - 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 operation is not supported by the implementing class
• #### getBatchLCASet

default List<Set<V>> getBatchLCASet​(List<Pair<V,​V>> queries)
Return a list of computed sets of LCAs for a batch of queries
Parameters:
queries - a list of pairs of vertices
Returns:
a list L of LCAs where L(i) is the computed set of LCAs for pair queries(i)