Package | Description |
---|---|
de.citec.tcs.alignment.forests |
This package contains tree edit distance algorithms for forests.
|
de.citec.tcs.alignment.trees |
This package contains an implementation of the Tree Edit Distance according to Zhang & Shasha (1989).
|
Modifier and Type | Method and Description |
---|---|
Comparator<Tree<X>,Tree<Y>> |
AbstractForestAlgorithm.getComparator() |
Comparator<Tree<X>,Tree<Y>> |
AbstractForestAlgorithm.getComparator() |
Alignment<Tree<X>,Tree<Y>> |
UnorderedForestFullAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Alignment<Tree<X>,Tree<Y>> |
UnorderedForestFullAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
UnorderedForestCooptimalAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
UnorderedForestCooptimalAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
OrderedForestCooptimalAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
OrderedForestCooptimalAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Alignment<Tree<X>,Tree<Y>> |
OrderedForestFullAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Alignment<Tree<X>,Tree<Y>> |
OrderedForestFullAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
OrderedForestSoftAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
OrderedForestSoftAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
UnorderedForestSoftAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
UnorderedForestSoftAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Modifier and Type | Method and Description |
---|---|
R |
AbstractForestAlgorithm.calculateAlignment(List<Tree<X>> X,
List<Tree<Y>> Y) |
R |
AbstractForestAlgorithm.calculateAlignment(List<Tree<X>> X,
List<Tree<Y>> Y) |
void |
UnorderedForestFullAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
UnorderedForestFullAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
UnorderedForestCooptimalAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
UnorderedForestCooptimalAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
OrderedForestCooptimalAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
OrderedForestCooptimalAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
OrderedForestFullAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
OrderedForestFullAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
OrderedForestSoftAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
OrderedForestSoftAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
UnorderedForestSoftAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
UnorderedForestSoftAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
AbstractForestAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
AbstractForestAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
Alignment<Tree<X>,Tree<Y>> |
UnorderedForestFullAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Alignment<Tree<X>,Tree<Y>> |
UnorderedForestFullAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
UnorderedForestCooptimalAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
UnorderedForestCooptimalAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
OrderedForestCooptimalAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
OrderedForestCooptimalAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Alignment<Tree<X>,Tree<Y>> |
OrderedForestFullAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Alignment<Tree<X>,Tree<Y>> |
OrderedForestFullAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
OrderedForestSoftAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
OrderedForestSoftAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
UnorderedForestSoftAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
UnorderedForestSoftAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Double |
UnorderedForestScoreAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Double |
UnorderedForestScoreAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Double |
OrderedForestScoreAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
Double |
OrderedForestScoreAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y) |
abstract R |
AbstractForestAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y)
Transforms the pairwise tree edit distances between the trees in the left and right forest to
an overall forest edit distance.
|
abstract R |
AbstractForestAlgorithm.transformToResult(double[][] rep,
double[] del,
double[] ins,
List<Tree<X>> X,
List<Tree<Y>> Y)
Transforms the pairwise tree edit distances between the trees in the left and right forest to
an overall forest edit distance.
|
static <X,Y> int |
UnorderedForestScoreAlgorithm.worstCaseDistance(List<Tree<X>> x,
List<Tree<Y>> y)
Returns the worst possible distance between the two input forests.
|
static <X,Y> int |
UnorderedForestScoreAlgorithm.worstCaseDistance(List<Tree<X>> x,
List<Tree<Y>> y)
Returns the worst possible distance between the two input forests.
|
static <X,Y> int |
OrderedForestScoreAlgorithm.worstCaseDistance(List<Tree<X>> X,
List<Tree<Y>> Y)
Returns the worst possible distance between the two input forests.
|
static <X,Y> int |
OrderedForestScoreAlgorithm.worstCaseDistance(List<Tree<X>> X,
List<Tree<Y>> Y)
Returns the worst possible distance between the two input forests.
|
Modifier and Type | Class and Description |
---|---|
class |
TreeImpl<X>
This is a bare-bones implementations of the Tree interface which can be used in case no own
Tree class is employed.
|
Modifier and Type | Method and Description |
---|---|
static <X> Tree<X> |
TreeProperties.getSubtree(List<Tree<X>> forest,
int... path)
Retrieves the subtree of the given forest corresponding to the given path from the root node.
|
static <X> Tree<X> |
TreeProperties.getSubtree(List<Tree<X>> forest,
List<Integer> path)
Retrieves the subtree of the given forest corresponding to the given path from the root node.
|
static <X> Tree<X> |
TreeProperties.getSubtree(Tree<X> tree,
int... path)
Retrieves the subtree of the given tree corresponding to the given path from the root node.
|
static <X> Tree<X> |
TreeProperties.getSubtree(Tree<X> tree,
List<Integer> path)
Retrieves the subtree of the given tree corresponding to the given path from the root node.
|
Tree<X> |
TreeImpl.ForestBuilder.getTree()
Returns the constructed tree.
|
Modifier and Type | Method and Description |
---|---|
Alignment<Tree<X>,Tree<Y>> |
TreeEditFullAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
Alignment<Tree<X>,Tree<Y>> |
TreeEditFullAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
TreeEditSoftAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
TreeEditSoftAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
TreeEditCooptimalAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
TreeEditCooptimalAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
List<Tree<X>> |
TreeImpl.getChildren() |
List<Tree<X>> |
Tree.getChildren()
Returns the children of the root node of this tree.
|
Comparator<Tree<X>,Tree<Y>> |
TreeEditAlgorithm.getComparator()
This should return the Comparator d used to compute the operation costs for this
TreeEditAlgorithm.
|
Comparator<Tree<X>,Tree<Y>> |
TreeEditAlgorithm.getComparator()
This should return the Comparator d used to compute the operation costs for this
TreeEditAlgorithm.
|
Comparator<Tree<X>,Tree<Y>> |
AbstractTreeEditAlgorithm.getComparator() |
Comparator<Tree<X>,Tree<Y>> |
AbstractTreeEditAlgorithm.getComparator() |
List<Tree<X>> |
TreeImpl.ForestBuilder.getCurrent()
Returns the current child forest of the constructed forest.
|
List<Tree<X>> |
TreeImpl.ForestBuilder.getForest()
Returns the constructed forest.
|
static <X> List<Tree<X>> |
TreeProperties.preOrder(List<Tree<X>> forest)
Returns all subtrees in the given forest in pre-oder.
|
static <X> List<Tree<X>> |
TreeProperties.preOrder(Tree<X> tree)
Returns all subtrees in the given treee in pre-oder.
|
Modifier and Type | Method and Description |
---|---|
static <X> int[][] |
TreeProperties.adjacencyList(Tree<X> tree)
Creates an array of arrays mapping pre-order indices of all nodes in the given tree to
the pre-order indices of their respective children in the given tree.
|
Double |
TreeEditScoreAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
Double |
TreeEditScoreAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
R |
TreeEditAlgorithm.calculateAlignment(Tree<X> x,
Tree<Y> y)
This calculates the tree edit distance D between the trees x ∈ T(X) and y ∈
T(Y) and returns it as an instance of the result class for this algorithm.
|
R |
TreeEditAlgorithm.calculateAlignment(Tree<X> x,
Tree<Y> y)
This calculates the tree edit distance D between the trees x ∈ T(X) and y ∈
T(Y) and returns it as an instance of the result class for this algorithm.
|
Alignment<Tree<X>,Tree<Y>> |
TreeEditFullAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
Alignment<Tree<X>,Tree<Y>> |
TreeEditFullAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
TreeEditSoftAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
TreeEditSoftAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
TreeEditCooptimalAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
CooptimalMatrix<Tree<X>,Tree<Y>> |
TreeEditCooptimalAlgorithm.calculateAlignment(Tree<X> X,
Tree<Y> Y) |
double |
LabelComparator.compare(OperationType type,
Tree<X> a,
Tree<Y> b) |
double |
LabelComparator.compare(OperationType type,
Tree<X> a,
Tree<Y> b) |
double |
DerivableLabelComparator.compare(OperationType type,
Tree<X> a,
Tree<Y> b) |
double |
DerivableLabelComparator.compare(OperationType type,
Tree<X> a,
Tree<Y> b) |
Gradient |
DerivableLabelComparator.computeGradient(OperationType type,
Tree<X> a,
Tree<Y> b) |
Gradient |
DerivableLabelComparator.computeGradient(OperationType type,
Tree<X> a,
Tree<Y> b) |
static <X> Tree<X> |
TreeProperties.getSubtree(Tree<X> tree,
int... path)
Retrieves the subtree of the given tree corresponding to the given path from the root node.
|
static <X> Tree<X> |
TreeProperties.getSubtree(Tree<X> tree,
List<Integer> path)
Retrieves the subtree of the given tree corresponding to the given path from the root node.
|
static <X> List<Tree<X>> |
TreeProperties.preOrder(Tree<X> tree)
Returns all subtrees in the given treee in pre-oder.
|
static <X> int |
TreeProperties.size(Tree<X> tree)
Returns the number of nodes in the given tree.
|
static <X,Y> int |
AbstractTreeEditAlgorithm.worstCaseDistance(Tree<X> X,
Tree<Y> Y)
Computes the worst-case tree edit distance between two trees X and Y, if a comparator would
be used that always returns 1.
|
static <X,Y> int |
AbstractTreeEditAlgorithm.worstCaseDistance(Tree<X> X,
Tree<Y> Y)
Computes the worst-case tree edit distance between two trees X and Y, if a comparator would
be used that always returns 1.
|
Modifier and Type | Method and Description |
---|---|
static <X> int[][] |
TreeProperties.adjacencyList(List<Tree<X>> forest)
Creates an array of arrays mapping pre-order indices of all nodes in the given forest to
the pre-order indices of their respective children in the given forest.
|
static <X> Tree<X> |
TreeProperties.getSubtree(List<Tree<X>> forest,
int... path)
Retrieves the subtree of the given forest corresponding to the given path from the root node.
|
static <X> Tree<X> |
TreeProperties.getSubtree(List<Tree<X>> forest,
List<Integer> path)
Retrieves the subtree of the given forest corresponding to the given path from the root node.
|
static <X> List<Tree<X>> |
TreeProperties.preOrder(List<Tree<X>> forest)
Returns all subtrees in the given forest in pre-oder.
|
void |
TreeEditAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator)
This should set the Comparator used to compute the operation costs for this
TreeEditAlgorithm.
|
void |
TreeEditAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator)
This should set the Comparator used to compute the operation costs for this
TreeEditAlgorithm.
|
void |
AbstractTreeEditAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
void |
AbstractTreeEditAlgorithm.setComparator(Comparator<Tree<X>,Tree<Y>> comparator) |
static <X> int |
TreeProperties.size(List<Tree<X>> forest)
Returns the number of nodes in the given forest.
|
Copyright (C) 2016-2018 Benjamin Paaßen, AG Theoretical Computer Science, Centre of Excellence Cognitive Interaction Technology (CITEC), University of Bielefeld, licensed under the AGPL v. 3: http://openresearch.cit-ec.de/projects/tcs . This documentation is licensed under the conditions of CC-BY-SA 4.0: https://creativecommons.org/licenses/by-sa/4.0/