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 java.util.List<V> getBatchLCA​(java.util.List<Pair<V,​V>> queries)
    Return a list of LCAs for a batch of queries
    default java.util.List<java.util.Set<V>> getBatchLCASet​(java.util.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
    java.util.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 java.util.List<V> getBatchLCA​(java.util.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

      java.util.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:
      java.lang.UnsupportedOperationException - - if the operation is not supported by the implementing class

    • getBatchLCASet

      default java.util.List<java.util.Set<V>> getBatchLCASet​(java.util.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)