Module org.jgrapht.core
Package org.jgrapht.alg.interfaces

Interface LowestCommonAncestorAlgorithm<V>

Type Parameters:
V - vertex the graph vertex type
All Known Implementing Classes:
BinaryLiftingLCAFinder, EulerTourRMQLCAFinder, HeavyPathLCAFinder, NaiveLCAFinder, TarjanLCAFinder
public interface LowestCommonAncestorAlgorithm<V>
Algorithm to compute a lowest common ancestor in a tree, forest or DAG.
Author:
Alexandru Valeanu

  • Method Summary

    Modifier and Type
    Method
    Description
    default List<V>
    getBatchLCA(List<Pair<V,V>> queries)
    Return a list of LCAs for a batch of queries
    default List<Set<V>>
    getBatchLCASet(List<Pair<V,V>> queries)
    Return a list of computed sets of LCAs for a batch of queries
    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

  • Method Details

    • getLCA

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

    • getBatchLCA

      default List<V> getBatchLCA(List<Pair<V,V>> queries)
      Return a list of LCAs for a batch of queries
      Parameters:
      queries - a list of pairs of vertices
      Returns:
      a list L of LCAs where L(i) is the LCA for pair queries(i)

    • getLCASet

      Set<V> getLCASet(V a, V b)
      Return the computed set of LCAs of a and b
      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:
      UnsupportedOperationException - - if the operation is not supported by the implementing class

    • getBatchLCASet

      default List<Set<V>> getBatchLCASet(List<Pair<V,V>> queries)
      Return a list of computed sets of LCAs for a batch of queries
      Parameters:
      queries - a list of pairs of vertices
      Returns:
      a list L of LCAs where L(i) is the computed set of LCAs for pair queries(i)