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

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