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>
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 incomputeKeyrootsAndMapping()
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 fromtree
whihc has ordering index equal to $i$.(package private) java.util.List<V>
indexToVertexList
List which at very position $i$ stores a vertex fromtree
which has ordering index equal to $i$.(package private) java.util.List<java.lang.Integer>
keyroots
List of keyroots oftree
.(package private) Graph<V,E>
tree
Underlying tree of this ordering.(package private) V
treeRoot
Root vertex oftree
.
-
Constructor Summary
Constructors Constructor Description TreeOrdering(Graph<V,E> tree, V treeRoot)
Constructs an instance of the tree ordering for the givengraph
andtreeRoot
.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
computeKeyrootsAndMapping(V treeRoot)
Runs post-order DFS ontree
starting attreeRoot
.
-
-
-
Field Detail
-
treeRoot
final V treeRoot
Root vertex oftree
.
-
keyroots
java.util.List<java.lang.Integer> keyroots
List of keyroots oftree
.
-
indexToVertexList
java.util.List<V> indexToVertexList
List which at very position $i$ stores a vertex fromtree
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 fromtree
whihc has ordering index equal to $i$.
-
currentIndex
int currentIndex
Ordering index to be assigned to the next traversed vertex.
-
-
Method Detail
-
computeKeyrootsAndMapping
private void computeKeyrootsAndMapping(V treeRoot)
Runs post-order DFS ontree
starting attreeRoot
. Assigns consecutive integer index to every traversed vertex and computes keyroots fortree
.- Parameters:
treeRoot
- root vertex oftree
-
-