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.

Method Summary

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 Details

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)