## Class 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 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). This naive algorithm simply starts at $a$ and $b$, recursing upwards to the root(s) of the DAG. Wherever the recursion paths cross we have found our LCA. 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. Start at each of nodes you wish to find the lca for (a and b)
2. Create sets aSet containing a, and bSet containing b
3. If either set intersects with the union of the other sets previous values (i.e. the set of notes visited) then
that intersection is LCA. if there are multiple intersections then the earliest one added is the LCA.
4. Repeat from step 3, with aSet now the parents of everything in aSet, and bSet the parents of everything in bSet
5. If there are no more parents to descend to then there is no LCA

The rationale for this working is that in each iteration of the loop we are considering all the ancestors of a that have a path of length n back to a, where n is the depth of the recursion. The same is true of b.

We start by checking if a == b.
if not we look to see if there is any intersection between parents(a) and (parents(b) union b) (and the same with a and b swapped)
if not we look to see if there is any intersection between parents(parents(a)) and (parents(parents(b)) union parents(b) union b) (and the same with a and b swapped)
continues

This means at the end of recursion n, we know if there is an LCA that has a path of <=n to a and b. Of course we may have to wait longer if the path to a is of length n, but the path to b>n. at the first loop we have a path of 0 length from the nodes we are considering as LCA to their respective children which we wish to find the LCA for.

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