Module org.jgrapht.core
Package org.jgrapht.alg.lca

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

    • NaiveLCAFinder

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

  • Method Details

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