 java.lang.Object

 org.jgrapht.alg.lca.BinaryLiftingLCAFinder<V,E>

 Type Parameters:
V
 the graph vertex typeE
 the graph edge type
 All Implemented Interfaces:
LowestCommonAncestorAlgorithm<V>
public class BinaryLiftingLCAFinder<V,E> extends java.lang.Object implements LowestCommonAncestorAlgorithm<V>
Algorithm for computing lowest common ancestors in rooted trees and forests using the binary lifting method.The method appears in Bender, Michael A., and Martın FarachColton. "The level ancestor problem simplified." Theoretical Computer Science 321.1 (2004): 512 and it is also nicely presented in the following article on Topcoder for more details about the algorithm.
Algorithm idea:
We improve on the naive approach by using jump pointers. These are pointers at a node which reference one of the node’s ancestors. Each node stores jump pointers to ancestors at levels 1, 2, 4, . . . , 2^k.
Queries are answered by repeatedly jumping from node to node, each time jumping more than half of the remaining levels between the current ancestor and the goal ancestor (i.e. the lca). The worstcase number of jumps is $O(log(V))$.Preprocessing Time complexity: $O(V log(V))$
Preprocessing Space complexity: $O(V log(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.
Spacewise,HeavyPathLCAFinder
andTarjanLCAFinder
only use a linear amount whileBinaryLiftingLCAFinder
andEulerTourRMQLCAFinder
require linearithmic space.
For DAGs, useNaiveLCAFinder
. Author:
 Alexandru Valeanu


Constructor Summary
Constructors Constructor Description BinaryLiftingLCAFinder(Graph<V,E> graph, java.util.Set<V> roots)
Construct a new instance of the algorithm.BinaryLiftingLCAFinder(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 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




Constructor Detail

BinaryLiftingLCAFinder
public BinaryLiftingLCAFinder(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

BinaryLiftingLCAFinder
public BinaryLiftingLCAFinder(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

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

