com.yworks.yfiles.algorithms

Class Trees

java.lang.Object

com.yworks.yfiles.algorithms.Trees

public final class Trees
extends 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

Modifier and Type	Method and Description
static void	collectSubtree(Node root, NodeList nodes) Collects all nodes of the subtree starting from the given root node.
static EdgeList	directTree(Graph tree) Converts the given tree to a directed rooted tree with the given node as root element 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, INodeMap subtreeDepthMap) Returns the depths of each subtree of a rooted directed tree.
static void	getSubTreeSizes(Graph tree, INodeMap 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) Returns an array of EdgeList objects each containing edges that belong to a maximal directed subtree of the given 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 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, INodeMap 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

collectSubtree

public static final void collectSubtree(Node root,
                                        NodeList nodes)

Collects all nodes of the subtree starting from the given root node.

Parameters:

root - the given root node

nodes - the NodeList that will be filled with the nodes of the subtree

directTree

public static final EdgeList directTree(Graph tree)

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

Returns:

an EdgeList containing the reversed edges

directTree

public static final 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

getCenterRoot

public static final 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

getLeafNodes

public static final 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

getNearestCommonAncestor

public static final 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

getRoot

public static final 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(Graph, INodeMap).
• 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

getSubTreeDepths

public static final void getSubTreeDepths(Graph tree,
                                          INodeMap subtreeDepthMap)

Returns the depths of each subtree of a rooted directed tree.

Parameters:

tree - a rooted directed tree graph

subtreeDepthMap - the INodeMap that will be filled during the execution with the depth of the subtree rooted at each node

getSubTreeSizes

public static final void getSubTreeSizes(Graph tree,
                                         INodeMap subtreeSizeMap)

Returns the size (number of nodes) of each subtree of a rooted directed tree.

Parameters:

tree - a rooted directed tree graph

subtreeSizeMap - the INodeMap that will be filled during the execution with the size of the subtree rooted at each node

getTreeEdges

public static final EdgeList[] getTreeEdges(Graph graph)

Returns an array of EdgeList objects each containing edges that belong to a maximal directed subtree of the given graph.

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

Parameters:

graph - the given graph

Returns:

an array of EdgeList objects each containing edges that belong to a maximal subtree

getTreeEdges

public static final EdgeList[] getTreeEdges(Graph graph,
                                            NodeList[] treeNodes)

Returns an array of EdgeList objects each containing edges that belong to a maximal directed subtree of the given graph.

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

Parameters:

graph - the given graph

treeNodes - an array of NodeLists previously calculated by getTreeNodes(Graph)

Returns:

an array of EdgeList objects each containing edges that belong to a maximal subtree

getTreeNodes

public static final 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 final 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

getWeightedCenterNode

public static final Node getWeightedCenterNode(Graph tree)

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 INodeMap.

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 final Node getWeightedCenterNode(Graph tree,
                                               INodeMap 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 INodeMap.

Preconditions:

The given graph must be a tree (may be undirected).

The graph must be non-empty.

Parameters:

tree - the given tree

intWeight - the INodeMap that holds the number of paths per node

Returns:

a Node used by the greatest number of all undirected paths

isForest

public static final 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 final 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

isNaryTree

public static final 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 final 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 final 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