y.algo
Class Trees

java.lang.Object
  y.algo.Trees

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

See Also:

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 NodeLists 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