org.jgrapht.alg.lca

## Class TarjanLCAFinder<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
LowestCommonAncestorAlgorithm<V>

public class TarjanLCAFinder<V,E>
extends Object
implements LowestCommonAncestorAlgorithm<V>
Tarjan's offline algorithm for computing lowest common ancestors in rooted trees and forests.

The original algorithm can be found in Gabow, H. N.; Tarjan, R. E. (1983), "A linear-time algorithm for a special case of disjoint set union", Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), pp. 246–251, doi:10.1145/800061.808753

Preprocessing Time complexity: $O(1)$
Preprocessing Space complexity: $O(1)$
Query Time complexity: $O(|V| log^{*}(|V|) + |Q|)$ where $|Q|$ is the number of queries
Query Space complexity: $O(|V| + |Q|)$ where $|Q|$ is the number of queries

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.

Author:
Alexandru Valeanu
• ### Constructor Detail

• #### TarjanLCAFinder

public TarjanLCAFinder(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 graph
root - the root of the graph
• #### TarjanLCAFinder

public TarjanLCAFinder(Graph<V,E> graph,
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 graph
roots - the set of roots of the graph
• ### Method Detail

• #### getLCA

public V getLCA(V a,
V b)
Return the LCA of a and b
Specified by:
getLCA in interface LowestCommonAncestorAlgorithm<V>
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

public List<V> getBatchLCA(List<Pair<V,V>> queries)
Return a list of LCAs for a batch of queries
Specified by:
getBatchLCA in interface LowestCommonAncestorAlgorithm<V>
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

public 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 interface LowestCommonAncestorAlgorithm<V>
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 method is called