public class TreeProperties extends Object
Modifier and Type | Method and Description |
---|---|
static <X> int[][] |
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> int[][] |
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.
|
static <X> Tree<X> |
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> |
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> |
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> |
getSubtree(Tree<X> tree,
List<Integer> path)
Retrieves the subtree of the given tree corresponding to the given path from the root node.
|
static Map<Integer,Integer> |
keyRootMap(int[] r)
Generates a map from outermost right descendant indices to key roots.
|
static int[] |
keyRoots(int[] r)
Generates the array of key roots for the given outermost right descendant indices.
|
static int[] |
outerMostRightDescendants(int[][] adj)
Returns an array mapping node pre-order indices to the pre-order indices of their outermost
right descendant in the given adjacency list.
|
static <X> List<Tree<X>> |
preOrder(List<Tree<X>> forest)
Returns all subtrees in the given forest in pre-oder.
|
static <X> List<Tree<X>> |
preOrder(Tree<X> tree)
Returns all subtrees in the given treee in pre-oder.
|
static <X> int |
size(List<Tree<X>> forest)
Returns the number of nodes in the given forest.
|
static <X> int |
size(Tree<X> tree)
Returns the number of nodes in the given tree.
|
public static <X> Tree<X> getSubtree(@NonNull Tree<X> tree, @NonNull List<Integer> path)
X
- the label class of the given tree.tree
- a tree.path
- a path identifying the position of a subtree in the given tree. The path is a
list of child indices which basically tells us how we have to navigate in the tree.public static <X> Tree<X> getSubtree(@NonNull Tree<X> tree, int... path)
X
- the label class of the given tree.tree
- a tree.path
- a path identifying the position of a subtree in the given tree. The path is an
array of child indices which basically tells us how we have to navigate in the tree.public static <X> Tree<X> getSubtree(@NonNull List<Tree<X>> forest, @NonNull List<Integer> path)
X
- the label class of the given forest.forest
- a forest.path
- a path identifying the position of a subtree in the given forest. The path is a
list of child indices which basically tells us how we have to navigate in the forest.public static <X> Tree<X> getSubtree(@NonNull List<Tree<X>> forest, @NonNull int... path)
X
- the label class of the given forest.forest
- a forest.path
- a path identifying the position of a subtree in the given forest. The path is an
array of child indices which basically tells us how we have to navigate in the forest.public static <X> int size(@NonNull List<Tree<X>> forest)
X
- the label class of the given forest.forest
- a forest.public static <X> int size(Tree<X> tree)
X
- the label class of the given tree.tree
- a tree.public static <X> List<Tree<X>> preOrder(@NonNull List<Tree<X>> forest)
X
- the label class of the given forest.forest
- a forest.public static <X> List<Tree<X>> preOrder(Tree<X> tree)
X
- the label class of the given tree.tree
- a tree.public static <X> int[][] adjacencyList(@NonNull List<Tree<X>> forest)
X
- the label class of the given forest.forest
- a forest.public static <X> int[][] adjacencyList(Tree<X> tree)
X
- the label class of the given tree.tree
- a tree.public static int[] outerMostRightDescendants(@NonNull int[][] adj)
adj
- an adjacency list.public static Map<Integer,Integer> keyRootMap(int[] r)
r
- the array of outermost right descendants for each node in the tree.public static int[] keyRoots(int[] r)
r
- the array of outermost right descendants for each node in the tree.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/