Class ZhangShashaTreeEditDistance.TreeOrdering

  • Enclosing class:
    ZhangShashaTreeEditDistance<V,​E>

    private class ZhangShashaTreeEditDistance.TreeOrdering
    extends java.lang.Object
    Auxiliary class which for computes keyroot vertices, tree ordering and $l()$ function for a particular tree.

    A keyroot of a tree is a vertex which has a left sibling. Ordering of a tree assings an integer index to every its vertex. Indices are assigned using post-order traversal. $l()$ function for every vertex in a tree returns ordering index of its leftmost child. For leaf vertex the function returns its own ordering index.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      private class  ZhangShashaTreeEditDistance.TreeOrdering.StackEntry
      Auxiliary class which stores all needed variables to emulate recursive execution of DFS algorithm in computeKeyrootsAndMapping() method.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) int currentIndex
      Ordering index to be assigned to the next traversed vertex.
      (package private) java.util.List<java.lang.Integer> indexToLValueList
      List which at every position $i$ stores value of $l()$ function for a vertex from tree whihc has ordering index equal to $i$.
      (package private) java.util.List<V> indexToVertexList
      List which at very position $i$ stores a vertex from tree which has ordering index equal to $i$.
      (package private) java.util.List<java.lang.Integer> keyroots
      List of keyroots of tree.
      (package private) Graph<V,​E> tree
      Underlying tree of this ordering.
      (package private) V treeRoot
      Root vertex of tree.
    • Constructor Summary

      Constructors 
      Constructor Description
      TreeOrdering​(Graph<V,​E> tree, V treeRoot)
      Constructs an instance of the tree ordering for the given graph and treeRoot.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void computeKeyrootsAndMapping​(V treeRoot)
      Runs post-order DFS on tree starting at treeRoot.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • tree

        final Graph<V,​E> tree
        Underlying tree of this ordering.
      • treeRoot

        final V treeRoot
        Root vertex of tree.
      • keyroots

        java.util.List<java.lang.Integer> keyroots
        List of keyroots of tree.
      • indexToVertexList

        java.util.List<V> indexToVertexList
        List which at very position $i$ stores a vertex from tree which has ordering index equal to $i$.
      • indexToLValueList

        java.util.List<java.lang.Integer> indexToLValueList
        List which at every position $i$ stores value of $l()$ function for a vertex from tree whihc has ordering index equal to $i$.
      • currentIndex

        int currentIndex
        Ordering index to be assigned to the next traversed vertex.
    • Constructor Detail

      • TreeOrdering

        public TreeOrdering​(Graph<V,​E> tree,
                            V treeRoot)
        Constructs an instance of the tree ordering for the given graph and treeRoot.
        Parameters:
        tree - a tree
        treeRoot - root vertex of tree
    • Method Detail

      • computeKeyrootsAndMapping

        private void computeKeyrootsAndMapping​(V treeRoot)
        Runs post-order DFS on tree starting at treeRoot. Assigns consecutive integer index to every traversed vertex and computes keyroots for tree.
        Parameters:
        treeRoot - root vertex of tree