Module org.jgrapht.core
Package org.jgrapht.alg.similarity
Class ZhangShashaTreeEditDistance.TreeOrdering
java.lang.Object
org.jgrapht.alg.similarity.ZhangShashaTreeEditDistance.TreeOrdering
- Enclosing class:
ZhangShashaTreeEditDistance<V,
E>
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 ClassesModifier and TypeClassDescriptionprivate class
Auxiliary class which stores all needed variables to emulate recursive execution of DFS algorithm incomputeKeyrootsAndMapping()
method. -
Field Summary
FieldsModifier and TypeFieldDescription(package private) int
Ordering index to be assigned to the next traversed vertex.List which at every position $i$ stores value of $l()$ function for a vertex fromtree
whihc has ordering index equal to $i$.List which at very position $i$ stores a vertex fromtree
which has ordering index equal to $i$.List of keyroots oftree
.Underlying tree of this ordering.(package private) final V
Root vertex oftree
. -
Constructor Summary
ConstructorsConstructorDescriptionTreeOrdering
(Graph<V, E> tree, V treeRoot) Constructs an instance of the tree ordering for the givengraph
andtreeRoot
. -
Method Summary
Modifier and TypeMethodDescriptionprivate void
computeKeyrootsAndMapping
(V treeRoot) Runs post-order DFS ontree
starting attreeRoot
.
-
Field Details
-
tree
Underlying tree of this ordering. -
treeRoot
Root vertex oftree
. -
keyroots
List of keyroots oftree
. -
indexToVertexList
List which at very position $i$ stores a vertex fromtree
which has ordering index equal to $i$. -
indexToLValueList
List which at every position $i$ stores value of $l()$ function for a vertex fromtree
whihc has ordering index equal to $i$. -
currentIndex
int currentIndexOrdering index to be assigned to the next traversed vertex.
-
-
Constructor Details
-
TreeOrdering
Constructs an instance of the tree ordering for the givengraph
andtreeRoot
.- Parameters:
tree
- a treetreeRoot
- root vertex oftree
-
-
Method Details
-
computeKeyrootsAndMapping
Runs post-order DFS ontree
starting attreeRoot
. Assigns consecutive integer index to every traversed vertex and computes keyroots fortree
.- Parameters:
treeRoot
- root vertex oftree
-