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 
    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) 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$.
    (package private) List<V>
    indexToVertexList
    List which at very position $i$ stores a vertex from tree which has ordering index equal to $i$.
    (package private) List<Integer>
    keyroots
    List of keyroots of tree.
    (package private) final Graph<V,E>
    tree
    Underlying tree of this ordering.
    (package private) final 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

    Modifier and Type
    Method
    Description
    private void
    computeKeyrootsAndMapping(V treeRoot)
    Runs post-order DFS on tree starting at treeRoot.

    Methods inherited from class 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