## Class NaiveLCAFinder<V,​E>

• java.lang.Object
• org.jgrapht.alg.lca.NaiveLCAFinder<V,​E>
• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
LowestCommonAncestorAlgorithm<V>

public class NaiveLCAFinder<V,​E>
extends java.lang.Object
implements LowestCommonAncestorAlgorithm<V>
Find the Lowest Common Ancestor of a directed graph.

Find the LCA, defined as "Let $G = (V, E)$ be a DAG, and let $x, y \in V$. Let $G_{x,y}$ be the subgraph of $G$ induced by the set of all common ancestors of $x$ and $y$. Define SLCA (x, y) to be the set of out-degree 0 nodes (leafs) in $G_{x,y}$. The lowest common ancestors of $x$ and $y$ are the elements of SLCA (x, y). " from Michael A. Bender, Martín Farach-Colton, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin, Lowest common ancestors in trees and directed acyclic graphs, Journal of Algorithms, Volume 57, Issue 2, 2005, Pages 75-94, ISSN 0196-6774, https://doi.org/10.1016/j.jalgor.2005.08.001.

The algorithm:

1. Find ancestor sets for nodes $a$ and $b$.
2. Find their intersection.
3. Extract leaf nodes from the intersection set.
The algorithm is straightforward in the way it finds the LCA set by definition.

Preprocessing Time complexity: $O(1)$
Preprocessing Space complexity: $O(1)$
Query Time complexity: $O(|V|)$
Query Space complexity: $O(|V|)$

For trees or forests please use either BinaryLiftingLCAFinder, HeavyPathLCAFinder, EulerTourRMQLCAFinder or TarjanLCAFinder.

Author:
Leo Crawford, Alexandru Valeanu
• ### Constructor Summary

Constructors
Constructor Description
NaiveLCAFinder​(Graph<V,​E> graph)
Create a new instance of the naive LCA finder.
• ### Method Summary

All Methods
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)
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

• #### NaiveLCAFinder

public NaiveLCAFinder​(Graph<V,​E> graph)
Create a new instance of the naive LCA finder.
Parameters:
graph - the input 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)
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.