y.algo
Class Trees

java.lang.Object
  y.algo.Trees

public class Trees
extends Object

Provides diverse algorithms and services for tree-structured graphs or subgraphs.

Method Summary

static EdgeList	directTree(Graph tree) Reverses the edges of the given tree such that it is a directed rooted tree afterwards.
static EdgeList	directTree(Graph tree, Node root) Reverses the edges of the given tree such that it is a directed rooted tree with the given node as root element.
static Node	getCenterRoot(Graph tree) Returns the center node of an undirected unrooted tree.
static NodeList	getLeafNodes(Graph tree, boolean rooted) 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 the root node of a rooted tree (or reversed rooted tree) or a maximum weight center node as defined in getWeightedCenterNode(y.base.Graph) or another node if the graph is not a tree.
static void	getSubTreeDepths(Graph tree, NodeMap subtreeDepthMap) Returns for a rooted directed tree the depths of each of its subtrees.
static void	getSubTreeSizes(Graph tree, NodeMap subtreeSizeMap) Returns for a rooted directed tree the size (number of nodes) of each of its subtrees.
static EdgeList[]	getTreeEdges(Graph graph) Returns an array of EdgeList objects each containing edges of the given graph that belong to maximal tree leaves of the graph.
static EdgeList[]	getTreeEdges(Graph graph, NodeList[] treeNodes) Same as getTreeEdges(Graph) but more efficient if the treeNodes where calculated before by getTreeNodes(Graph).
static NodeList[]	getTreeNodes(Graph graph) Returns a list of NodeList objects each containing nodes of the given graph that belong to a maximal subtree of the graph.
static NodeList[]	getUndirectedTreeNodes(Graph graph) Returns a list of NodeList objects each containing nodes of the given graph that belong to a maximal subtree of the graph.
static Node	getWeightedCenterNode(Graph tree) Finds a node which is used by the greatest number of all paths interconnecting all nodes with each other.
static Node	getWeightedCenterNode(Graph tree, NodeMap intWeight) Finds a node which is used by the greatest number of all paths interconnecting all nodes with each other.
static boolean	isForest(Graph g) Checks whether the given graph is a forest, i.e.
static boolean	isNaryTree(Graph g, int n) Checks whether the given graph is a rooted tree where each node has a maximum of n successors.
static boolean	isRootedTree(Graph g) Checks whether the given graph is a rooted tree.
static boolean	isTree(Graph g) 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 of the given graph that belong to maximal tree leaves of the graph.

getTreeEdges

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

Same as getTreeEdges(Graph) but more efficient if the treeNodes where calculated before by getTreeNodes(Graph).

Parameters:

treeNodes - An array of NodeLists formerly calculated by getTreeNodes(Graph).

getTreeNodes

public static NodeList[] getTreeNodes(Graph graph)

Returns a list of NodeList objects each containing nodes of the given graph that belong to a maximal subtree of the 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 root's indegree is at least two.

getUndirectedTreeNodes

public static NodeList[] getUndirectedTreeNodes(Graph graph)

Returns a list of NodeList objects each containing nodes of the given graph that belong to a maximal subtree of the 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 root's indegree is at least two.

isNaryTree

public static boolean isNaryTree(Graph g,
                                 int n)

Checks whether the given graph is a rooted tree where each node has a maximum of n successors.

isRootedTree

public static boolean isRootedTree(Graph g)

Checks whether the given graph is a rooted tree.

isTree

public static boolean isTree(Graph g)

Checks whether or not the given graph is an undirected tree.

isForest

public static boolean isForest(Graph g)

Checks whether the given graph is a forest, i.e. a graph whose connected components are rooted trees.

getLeafNodes

public static NodeList getLeafNodes(Graph tree,
                                    boolean rooted)

Returns all leaf nodes of the given tree. A leaf node is a node with degree == 1 in an unrooted/undirected tree, and a node with outdegree == 0 in a rooted/directed tree. a

Parameters:

rooted - whether or not to consider the tree as rooted.

getCenterRoot

public static Node getCenterRoot(Graph tree)

Returns the center node of an undirected unrooted tree. the center node has the property of inducing a minimum depth tree when being used as the root of that tree.

Precondition:

!tree.isEmpty()

getRoot

public static Node getRoot(Graph tree)

Returns the root node of a rooted tree (or reversed rooted tree) or a maximum weight center node as defined in getWeightedCenterNode(y.base.Graph) or another node if the graph is not a tree.

Preconditions:

tree.isTree() or there is exactly one node with indegree == 0 or there is exactly one node with outdegree == 0

!tree.isEmpty()

directTree

public static EdgeList directTree(Graph tree)

Reverses the edges of the given tree such that it is a directed rooted tree afterwards.

Preconditions:

The given graph must be a tree.

!graph.isEmpty()

getWeightedCenterNode

public static Node getWeightedCenterNode(Graph tree)

Finds a node which is used by the greatest number of all paths interconnecting all nodes with each other.

Preconditions:

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

!graph.isEmpty()

getWeightedCenterNode

public static Node getWeightedCenterNode(Graph tree,
                                         NodeMap intWeight)

Finds a node which is used by the greatest number of all 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).

!graph.isEmpty()

directTree

public static EdgeList directTree(Graph tree,
                                  Node root)

Reverses the edges of the given tree such that it is a directed rooted tree with the given node as root element. 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

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.

Complexity:

O(tree.N())

Precondition:

isTree(tree)

getSubTreeDepths

public static void getSubTreeDepths(Graph tree,
                                    NodeMap subtreeDepthMap)

Returns for a rooted directed tree the depths of each of its subtrees.

Parameters:

tree - a rooted directed tree graph

subtreeDepthMap - node map that will hold for each node the depth of the subtree rooted at it. The resulting depth values can be retrieved using the map method NodeMap.getInt(Object).

getSubTreeSizes

public static void getSubTreeSizes(Graph tree,
                                   NodeMap subtreeSizeMap)

Returns for a rooted directed tree the size (number of nodes) of each of its subtrees.

Parameters:

tree - a rooted directed tree graph

subtreeSizeMap - node map that will hold for each node the size of the subtree rooted at it. The resulting size values can be retrieved using the map method NodeMap.getInt(Object).