Search this API

## y.algo Class Trees

```java.lang.Object
y.algo.Trees
```

`public class Treesextends java.lang.Object`

This class provides diverse algorithms and services for tree-structured graphs or subgraphs.

### Definitions

• Tree: An acyclic graph, in which any pair of vertices (nodes) is connected through a path. If one vertex of a tree is distinguished from the other vertices, then this vertex is called the root and the tree is called a rooted tree.
• Directed rooted tree: A rooted tree where edges are directed from the root to the leaves.
• Depth: The depth of a vertex in a rooted tree is the number of edges of the unique path between this vertex and the root.
• Parent: In a rooted tree a vertex `v` is called parent of a vertex `w` if `v` and `w` are adjacent (i.e. connected by an edge) and the unique path between `w` and the root contains `v`. Note that each vertex except the root has exactly one parent.
• Children: In a rooted tree a vertex `w` is called child of a vertex `v` if `v` is the parent of `w`. A vertex may have several children.
• N-ary tree: A directed rooted tree where each node has a maximum of `n` children.
• Forest: A graph whose connected components are trees.
• Leaf: A leaf `v` is a node with out-degree (i.e., the number of edges having `v` as a target) zero if the input is a directed rooted tree, and a node with degree (i.e., the number of edges incident to `v`) one, otherwise.
• Subtree: A subtree of a tree `T` is a subgraph of `T` which is also a tree.
• Nearest or Lowest or Least common ancestor: The nearest common ancestor of two nodes `u` and `v` in a tree graph is the shared ancestor of `u` and `v` that is located farthest from the root.
• Eccentricity: The eccentricity of a tree node is the maximum distance to any other node.
• Center node: The center of a tree is the set of nodes that have minimal eccentricity.

Method Summary
`static void` ```collectSubtree(Node root, NodeList nodes)```
Collects all nodes of the subtree starting with root.
`static EdgeList` `directTree(Graph tree)`
Converts a given tree to a directed rooted tree by reversing some edges.
`static EdgeList` ```directTree(Graph tree, Node root)```
Converts the given tree to a directed rooted tree with the given node as root element by reversing some edges.
`static Node` `getCenterRoot(Graph tree)`
Returns the center node of an undirected tree.
`static NodeList` ```getLeafNodes(Graph tree, boolean directedRootedTree)```
Returns all leaf nodes of the given tree.
`static Node` ```getNearestCommonAncestor(Graph tree, Node root, boolean rootedDownward, NodeList nodes)```
Returns the nearest common ancestor of a subset of nodes within a directed rooted tree.
`static Node` `getRoot(Graph tree)`
Returns a possible root for the given (undirected) tree.
`static void` ```getSubTreeDepths(Graph tree, NodeMap subtreeDepthMap)```
Returns the depths of each subtree of a rooted directed tree.
`static void` ```getSubTreeSizes(Graph tree, NodeMap subtreeSizeMap)```
Returns the size (number of nodes) of each subtree of a rooted directed tree.
`static EdgeList[]` `getTreeEdges(Graph graph)`
Returns an array of `EdgeList` objects each containing edges that belong to a maximal directed subtree of the given graph.
`static EdgeList[]` ```getTreeEdges(Graph graph, NodeList[] treeNodes)```
Same as `getTreeEdges(Graph)` but more efficient if the list of tree nodes is calculated before by `getTreeNodes(Graph)`.
`static NodeList[]` `getTreeNodes(Graph graph)`
Returns an array of `NodeList` objects each containing nodes that belong to a maximal directed subtree of the given graph.
`static NodeList[]` `getUndirectedTreeNodes(Graph graph)`
Returns an array of `NodeList` objects each containing nodes that belong to a maximal undirected subtree of the given graph.
`static NodeList[]` ```getUndirectedTreeNodes(Graph graph, DataProvider edgeSelectorDP)```
Returns an array of `NodeList` objects each containing nodes that belong to a maximal undirected subtree of the given graph only considering edge for which method `DataProvider.getBool(Object)` of the specified `DataProvider` returns `true`.
`static Node` `getWeightedCenterNode(Graph tree)`
Finds a node used by the greatest number of all (undirected) paths interconnecting all nodes with each other.
`static Node` ```getWeightedCenterNode(Graph tree, NodeMap intWeight)```
Finds a node used by the greatest number of all (undirected) paths interconnecting all nodes with each other.
`static boolean` `isForest(Graph graph)`
Checks whether or not the given graph is a forest, that is, a graph whose connected components are directed rooted trees.
`static boolean` ```isForest(Graph graph, boolean directedRootedTree)```
Checks whether or not the given graph is a forest.
`static boolean` ```isNaryTree(Graph graph, int n)```
Checks whether or not the given graph is a directed rooted tree in which each node has a maximum of `n` children.
`static boolean` `isRootedTree(Graph graph)`
Checks whether or not the given graph is a directed rooted tree.
`static boolean` `isTree(Graph graph)`
Checks whether or not the given graph is an undirected tree.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Method Detail

### getTreeEdges

`public static EdgeList[] getTreeEdges(Graph graph)`
Returns an array of `EdgeList` objects each containing edges that belong to a maximal directed subtree of the given graph.

Parameters:
`graph` - the given graph
Returns:
an array of `EdgeList` objects each containing edges that belong to a maximal directed subtree
`getTreeNodes(y.base.Graph)`

### getTreeEdges

```public static EdgeList[] getTreeEdges(Graph graph,
NodeList[] treeNodes)```
Same as `getTreeEdges(Graph)` but more efficient if the list of tree nodes is calculated before by `getTreeNodes(Graph)`.

Furthermore, this method can also be applied to the result obtained by `getUndirectedTreeNodes(y.base.Graph)`. In this case, the subtrees are considered to be undirected.

Parameters:
`graph` - the given graph
`treeNodes` - an array of `NodeList`s previously calculated by `getTreeNodes(Graph)`
Returns:
an array of `EdgeList` objects each containing edges that belong to a maximal subtree

### getTreeNodes

`public static NodeList[] getTreeNodes(Graph graph)`
Returns an array of `NodeList` objects each containing nodes that belong to a maximal directed subtree of the given graph.

For each list of tree nodes, the first node element is the root of a tree. On each such root, all outgoing edges connect to nodes in the subtree and each in-degree of the root is at least two.

Parameters:
`graph` - the given graph
Returns:
an array of `NodeList` objects each containing nodes that belong to a maximal directed subtree

### getUndirectedTreeNodes

`public static NodeList[] getUndirectedTreeNodes(Graph graph)`
Returns an array of `NodeList` objects each containing nodes that belong to a maximal undirected subtree of the given graph.

For each list of tree nodes, the first node is the only node of the subtree that may be incident to non-tree edges.

Parameters:
`graph` - the given graph
Returns:
an array of `NodeList` objects each containing nodes that belong to a maximal undirected subtree

### getUndirectedTreeNodes

```public static NodeList[] getUndirectedTreeNodes(Graph graph,
DataProvider edgeSelectorDP)```
Returns an array of `NodeList` objects each containing nodes that belong to a maximal undirected subtree of the given graph only considering edge for which method `DataProvider.getBool(Object)` of the specified `DataProvider` returns `true`.

For each list of tree nodes, the first node is the only node of the subtree that may be incident to non-tree edges.

Parameters:
`graph` - the given graph
`edgeSelectorDP` - we consider only edges for which `DataProvider.getBool(Object)` returns `true`
Returns:
an array of `NodeList` objects each containing nodes that belong to a maximal undirected subtree

### isNaryTree

```public static boolean isNaryTree(Graph graph,
int n)```
Checks whether or not the given graph is a directed rooted tree in which each node has a maximum of `n` children.

Parameters:
`graph` - the given graph
`n` - the allowed maximum of children
Returns:
`true` if the given graph is a n-ary tree, `false` otherwise

### isRootedTree

`public static boolean isRootedTree(Graph graph)`
Checks whether or not the given graph is a directed rooted tree.

`isRootedTree(graph) => isTree(graph)`
Parameters:
`graph` - the given graph
Returns:
`true` if the given graph is a directed rooted tree, `false` otherwise

### isTree

`public static boolean isTree(Graph graph)`
Checks whether or not the given graph is an undirected tree.

`isRootedTree(graph) => isTree(graph)`.
Parameters:
`graph` - the given graph
Returns:
`true` if the given graph is an undirected tree, `false` otherwise

### isForest

`public static boolean isForest(Graph graph)`
Checks whether or not the given graph is a forest, that is, a graph whose connected components are directed rooted trees.

Parameters:
`graph` - the given graph
Returns:
`true` if the given graph is a forest, `false` otherwise

### isForest

```public static boolean isForest(Graph graph,
boolean directedRootedTree)```
Checks whether or not the given graph is a forest.

If `directedRootedTree == true`, each component has to be a directed rooted tree. Otherwise, each component has to be an undirected tree.

`isForest(graph, true) => isForest(graph, false)`
Parameters:
`graph` - the given graph
`directedRootedTree` - `true` if the algorithm should check for directed rooted trees, `false` otherwise
Returns:
`true` if the given graph is a forest, `false` otherwise

### getLeafNodes

```public static NodeList getLeafNodes(Graph tree,
boolean directedRootedTree)```
Returns all leaf nodes of the given tree.

A leaf node is a node with `outdegree == 0` if the input is a directed rooted tree, and a node with `degree == 1`, otherwise.

Parameters:
`tree` - the given tree
`directedRootedTree` - `true` if the algorithm should consider the tree as directed, `false` otherwise
Returns:
a `NodeList` that contains all leaf nodes of the given tree

### getCenterRoot

`public static Node getCenterRoot(Graph tree)`
Returns the center node of an undirected tree.

The center node has the property of inducing a minimum depth tree when being used as the root of that tree.

Preconditions:
The graph must be `non-empty`.
The given graph must be a `tree`.
Parameters:
`tree` - the given undirected tree
Returns:
the center node of the given undirected tree

### getRoot

`public static Node getRoot(Graph tree)`
Returns a possible root for the given (undirected) tree.

More precisely:

• If the input is a directed rooted tree or reversed directed rooted tree, it returns the corresponding root node.
• If the input is a tree, the method returns a maximum weight center node as defined in `getWeightedCenterNode(y.base.Graph)`.
• If the input is not a tree, a node with `indegree == 0` (or `outdegree == 0`) is returned.

Preconditions:
The given graph must be a `tree`, or there is exactly one node with `indegree == 0`, or there is exactly one node with `outdegree == 0`
The graph must be `non-empty`.
Parameters:
`tree` - the given tree
Returns:
a possible root for the given tree

### directTree

`public static EdgeList directTree(Graph tree)`
Converts a given tree to a directed rooted tree by reversing some edges.

A list of all reversed edges will be returned by this method.

Preconditions:
The given graph must be a `tree`.
The graph must be `non-empty`.
Parameters:
`tree` - the given tree
Returns:
an `EdgeList` that contains the reversed edges

### getWeightedCenterNode

`public static Node getWeightedCenterNode(Graph tree)`
Finds a node used by the greatest number of all (undirected) paths interconnecting all nodes with each other.

Preconditions:
The given graph must be a `tree` (may be undirected).
The graph must be `non-empty`.
Parameters:
`tree` - the given tree
Returns:
a `Node` used by the greatest number of all undirected paths

### getWeightedCenterNode

```public static Node getWeightedCenterNode(Graph tree,
NodeMap intWeight)```
Finds a node used by the greatest number of all (undirected) paths interconnecting all nodes with each other.

The number of paths per node are stored in the given `NodeMap`.

Preconditions:
The given graph must be a `tree` (may be undirected).
The graph must be `non-empty`.
Parameters:
`tree` - the given tree
`intWeight` - the `NodeMap` that holds the number of paths per node
Returns:
a `Node` used by the greatest number of all undirected paths

### directTree

```public static EdgeList directTree(Graph tree,
Node root)```
Converts the given tree to a directed rooted tree with the given node as root element by reversing some edges.

A list of all reversed edges will be returned by this method.

Preconditions:
The given graph must be a `tree`.
The given node must be part of the given graph.
Parameters:
`tree` - the given tree
`root` - the given root element
Returns:
an `EdgeList` containing the reversed edges

### collectSubtree

```public static void collectSubtree(Node root,
NodeList nodes)```
Collects all nodes of the subtree starting with root.

Parameters:
`root` - the root of the subtree
`nodes` - the list that is filled with the nodes of the subtree

### getNearestCommonAncestor

```public static Node getNearestCommonAncestor(Graph tree,
Node root,
boolean rootedDownward,
NodeList nodes)```
Returns the nearest common ancestor of a subset of nodes within a directed rooted tree.

It is not part of the given subset.

Precondition:
The given graph must be a `tree`.
Complexity:
`O(tree.N())`
Parameters:
`tree` - the given directed rooted tree
`root` - the root of the tree
`rootedDownward` - `true` if the tree is directed from the root to the leaves, `false` otherwise
`nodes` - the subset of nodes
Returns:
the `nearest common ancestor` of the given subset of nodes

### getSubTreeDepths

```public static void getSubTreeDepths(Graph tree,
NodeMap subtreeDepthMap)```
Returns the depths of each subtree of a rooted directed tree.

Parameters:
`tree` - a rooted directed tree graph
`subtreeDepthMap` - the `NodeMap` that will be filled during the execution with the depth of the subtree rooted at each node

### getSubTreeSizes

```public static void getSubTreeSizes(Graph tree,
NodeMap subtreeSizeMap)```
Returns the size (number of nodes) of each subtree of a rooted directed tree.

Parameters:
`tree` - a rooted directed tree graph
`subtreeSizeMap` - the `NodeMap` that will be filled during the execution with the size of the subtree rooted at each node