Class TarjanLowestCommonAncestor<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class TarjanLowestCommonAncestor<V,​E>
    extends java.lang.Object
    Used to calculate Tarjan's Lowest Common Ancestors Algorithm
    • Constructor Detail

      • TarjanLowestCommonAncestor

        public TarjanLowestCommonAncestor​(Graph<V,​E> g)
        Create an instance with a reference to the graph that we will find LCAs for
        Parameters:
        g - the input graph
    • Method Detail

      • calculate

        public V calculate​(V start,
                           V a,
                           V b)
        Calculate the LCM between a and b treating start as the root we want to search from.
        Parameters:
        start - the root of subtree
        a - the first vertex
        b - the second vertex
        Returns:
        the least common ancestor
      • calculate

        public java.util.List<V> calculate​(V start,
                                           java.util.List<TarjanLowestCommonAncestor.LcaRequestResponse<V>> lrr)
        Calculate the LCMs between a set of pairs (a and b) treating start as the root we want to search from, and setting the LCA of each pair in its LCA field
        Parameters:
        start - the root of the subtree
        lrr - a list of requests-response objects. The answer if stored on these objects at the LCA field.
        Returns:
        the LCMs