
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.Trees
public class Trees
This class provides diverse algorithms and services for treestructured graphs or subgraphs.
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.
w
is called child of a vertex v
if v
is the parent of w
. A vertex may have several children.
n
children.v
is a node with outdegree (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.
T
is a subgraph of T
which is also a tree.u
and v
in a tree graph is the shared ancestor of u
and v
that is located farthest
from the root.
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 

public static EdgeList[] getTreeEdges(Graph graph)
EdgeList
objects each containing edges that belong to a
maximal directed subtree of the given graph.
graph
 the given graph
EdgeList
objects each containing edges that belong to a maximal directed subtreegetTreeNodes(y.base.Graph)
public static EdgeList[] getTreeEdges(Graph graph, NodeList[] treeNodes)
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.
graph
 the given graphtreeNodes
 an array of NodeList
s previously calculated by getTreeNodes(Graph)
EdgeList
objects each containing edges that belong to a maximal subtreepublic static NodeList[] getTreeNodes(Graph graph)
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 indegree of the root is at least two.
graph
 the given graph
NodeList
objects each containing nodes that belong to a maximal directed subtreepublic static NodeList[] getUndirectedTreeNodes(Graph graph)
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 nontree edges.
graph
 the given graph
NodeList
objects each containing nodes that belong to a maximal undirected subtreepublic static NodeList[] getUndirectedTreeNodes(Graph graph, DataProvider edgeSelectorDP)
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 nontree edges.
graph
 the given graphedgeSelectorDP
 we consider only edges for which DataProvider.getBool(Object)
returns true
NodeList
objects each containing nodes that belong to a maximal undirected subtreepublic static boolean isNaryTree(Graph graph, int n)
n
children.
graph
 the given graphn
 the allowed maximum of children
true
if the given graph is a nary tree, false
otherwisepublic static boolean isRootedTree(Graph graph)
isRootedTree(graph) => isTree(graph)
graph
 the given graph
true
if the given graph is a directed rooted tree, false
otherwisepublic static boolean isTree(Graph graph)
isRootedTree(graph) => isTree(graph)
.graph
 the given graph
true
if the given graph is an undirected tree, false
otherwisepublic static boolean isForest(Graph graph)
graph
 the given graph
true
if the given graph is a forest, false
otherwisepublic static boolean isForest(Graph graph, boolean directedRootedTree)
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)
graph
 the given graphdirectedRootedTree
 true
if the algorithm should check for directed rooted trees,
false
otherwise
true
if the given graph is a forest, false
otherwisepublic static NodeList getLeafNodes(Graph tree, boolean directedRootedTree)
A leaf node is a node with outdegree == 0
if the input is a directed rooted tree,
and a node with degree == 1
, otherwise.
tree
 the given treedirectedRootedTree
 true
if the algorithm should consider the tree as directed,
false
otherwise
NodeList
that contains all leaf nodes of the given treepublic static Node getCenterRoot(Graph tree)
The center node has the property of inducing a minimum depth tree when being used as the root of that tree.
nonempty
.tree
.tree
 the given undirected tree
public static Node getRoot(Graph tree)
More precisely:
getWeightedCenterNode(y.base.Graph)
.
indegree == 0
(or outdegree == 0
) is returned.
tree
, or there is exactly one node with indegree == 0
,
or there is exactly one node with outdegree == 0
nonempty
.tree
 the given tree
public static EdgeList directTree(Graph tree)
A list of all reversed edges will be returned by this method.
tree
.nonempty
.tree
 the given tree
EdgeList
that contains the reversed edgespublic static Node getWeightedCenterNode(Graph tree)
tree
(may be undirected).nonempty
.tree
 the given tree
Node
used by the greatest number of all undirected pathspublic static Node getWeightedCenterNode(Graph tree, NodeMap intWeight)
The number of paths per node are stored in the given NodeMap
.
tree
(may be undirected).nonempty
.tree
 the given treeintWeight
 the NodeMap
that holds the number of paths per node
Node
used by the greatest number of all undirected pathspublic static EdgeList directTree(Graph tree, Node root)
A list of all reversed edges will be returned by this method.
tree
.tree
 the given treeroot
 the given root element
EdgeList
containing the reversed edgespublic static void collectSubtree(Node root, NodeList nodes)
root
 the root of the subtreenodes
 the list that is filled with the nodes of the subtreepublic static Node getNearestCommonAncestor(Graph tree, Node root, boolean rootedDownward, NodeList nodes)
It is not part of the given subset.
tree
.O(tree.N())
tree
 the given directed rooted treeroot
 the root of the treerootedDownward
 true
if the tree is directed from the root to the leaves, false
otherwisenodes
 the subset of nodes
nearest common ancestor
of the given subset of nodespublic static void getSubTreeDepths(Graph tree, NodeMap subtreeDepthMap)
tree
 a rooted directed tree graphsubtreeDepthMap
 the NodeMap
that will be filled during the execution with the depth of the
subtree rooted at each nodepublic static void getSubTreeSizes(Graph tree, NodeMap subtreeSizeMap)
tree
 a rooted directed tree graphsubtreeSizeMap
 the NodeMap
that will be filled during the execution with the size of the
subtree rooted at each node

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 