Class ZhangShashaTreeEditDistance.TreeOrdering

java.lang.Object
org.jgrapht.alg.similarity.ZhangShashaTreeEditDistance.TreeOrdering
Enclosing class:
ZhangShashaTreeEditDistance<V,E>

private class ZhangShashaTreeEditDistance.TreeOrdering extends 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 
    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
    Ordering index to be assigned to the next traversed vertex.
    (package private) List<Integer>
    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) List<V>
    List which at very position $i$ stores a vertex from tree which has ordering index equal to $i$.
    (package private) List<Integer>
    List of keyroots of tree.
    (package private) final Graph<V,E>
    Underlying tree of this ordering.
    (package private) final V
    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

    Modifier and Type
    Method
    Description
    private void
    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 Details

    • tree

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

      final V treeRoot
      Root vertex of tree.
    • keyroots

      List<Integer> keyroots
      List of keyroots of tree.
    • indexToVertexList

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

      List<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 Details

    • 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 Details

    • 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