Class HeavyPathLCAFinder<V,​E>

    • Field Detail

      • graph

        private final Graph<V,​E> graph
      • roots

        private final java.util.Set<V> roots
      • parent

        private int[] parent
      • depth

        private int[] depth
      • path

        private int[] path
      • positionInPath

        private int[] positionInPath
      • component

        private int[] component
      • firstNodeInPath

        private int[] firstNodeInPath
      • vertexMap

        private java.util.Map<V,​java.lang.Integer> vertexMap
      • indexList

        private java.util.List<V> indexList
    • Constructor Detail

      • HeavyPathLCAFinder

        public HeavyPathLCAFinder​(Graph<V,​E> graph,
                                  V root)
        Construct a new instance of the algorithm.

        Note: The constructor will NOT check if the input graph is a valid tree.

        Parameters:
        graph - the input graph
        root - the root of the graph
      • HeavyPathLCAFinder

        public HeavyPathLCAFinder​(Graph<V,​E> graph,
                                  java.util.Set<V> roots)
        Construct a new instance of the algorithm.

        Note: If two roots appear in the same tree, an error will be thrown.

        Note: The constructor will NOT check if the input graph is a valid forest.

        Parameters:
        graph - the input graph
        roots - the set of roots of the graph
    • Method Detail

      • computeHeavyPathDecomposition

        private void computeHeavyPathDecomposition()
        Compute the heavy path decomposition and get the corresponding arrays from the internal state.
      • 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 java.util.Set<V> getLCASet​(V a,
                                          V b)
        Note: This operation is not supported.
        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.
        Throws:
        java.lang.UnsupportedOperationException - if the method is called