Package org.jgrapht.alg.lca

Class HeavyPathLCAFinder<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

LowestCommonAncestorAlgorithm<V>

public class HeavyPathLCAFinder<V,E>
extends java.lang.Object
implements LowestCommonAncestorAlgorithm<V>

Algorithm for computing lowest common ancestors in rooted trees and forests based on 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.

Author:

Alexandru Valeanu

Constructor Summary

Constructors

Constructor	Description
HeavyPathLCAFinder(Graph<V,E> graph, java.util.Set<V> roots)	Construct a new instance of the algorithm.
HeavyPathLCAFinder(Graph<V,E> graph, V root)	Construct a new instance of the algorithm.

Method Summary

Modifier and Type	Method	Description
V	getLCA(V a, V b)	Return the LCA of a and b
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

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

HeavyPathLCAFinder

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

HeavyPathLCAFinder

public HeavyPathLCAFinder(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 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.

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 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:

java.lang.UnsupportedOperationException - if the method is called