Package | com.yworks.yfiles.algo |
Class | public class Trees |
Inheritance | Trees YObject Object |
Method | Defined By | ||
---|---|---|---|
Trees(init:Boolean = true) | Trees | ||
[static]
Reverses some edges of the given tree such that it is a directed rooted tree afterwards. | Trees | ||
[static]
Reverses some edges of the given tree such that it is a directed rooted tree with the given node as root element. | Trees | ||
equals(o:Object):Boolean | YObject | ||
[static]
Returns the center node of an undirected tree. | Trees | ||
getClass():Class [override] | Trees | ||
[static]
Returns all leaf nodes of the given tree. | Trees | ||
[static]
Returns the nearest common ancestor of a subset of nodes within a directed rooted tree. | Trees | ||
[static]
Returns a possible root for the given (undirected) tree. | Trees | ||
[static]
Returns for a rooted directed tree the depths of each of its subtrees. | Trees | ||
[static]
Returns for a rooted directed tree the size (number of nodes) of each of its subtrees. | Trees | ||
getTreeEdges(graph:Graph):Vector.<Object> [static]
Returns an array of EdgeList objects each containing edges that belong to a maximal directed subtree of the given graph. | Trees | ||
getTreeEdgesForTreeNodes(graph:Graph, treeNodes:Vector.<Object>):Vector.<Object> [static]
Same as getTreeEdges() but more efficient if the treeNodes where calculated before by getTreeNodes(). | Trees | ||
getTreeNodes(graph:Graph):Vector.<Object> [static]
Returns an array of NodeList objects each containing nodes that belong to a maximal directed subtree of the given graph. | Trees | ||
getUndirectedTreeNodes(graph:Graph):Vector.<Object> [static]
Returns an array of NodeList objects each containing nodes that belong to a maximal undirected subtree of the given graph. | Trees | ||
[static]
Finds a node which is used by the greatest number of all (undirected) paths interconnecting all nodes with each other. | Trees | ||
[static]
Finds a node which is used by the greatest number of all (undirected) paths interconnecting all nodes with each other. | Trees | ||
hashCode():int | YObject | ||
[static]
Checks whether the given graph is a forest, that is, a graph whose connected components are directed rooted trees. | Trees | ||
[static]
Checks whether the given graph is a forest. | Trees | ||
isNaryTree(g:Graph, n:int):Boolean [static]
Checks whether the given graph is a directed rooted tree where each node has a maximum of n children. | Trees | ||
isRootedTree(g:Graph):Boolean [static]
Checks whether the given graph is a directed rooted tree. | Trees | ||
[static]
Checks whether or not the given graph is an undirected tree. | Trees |
Trees | () | Constructor |
public function Trees(init:Boolean = true)
init:Boolean (default = true )
|
directTree | () | method |
public static function directTree(tree:Graph):EdgeList
Reverses some edges of the given tree such that it is a directed rooted tree afterwards. A list of all reversed edges will be returned by this method.
Precondition The given graph must be a tree.
Precondition
Parameters
tree:Graph — the given tree.
|
EdgeList — an com.yworks.yfiles.base.EdgeList that contains the reversed edges.
|
See also
directTreeWithRoot | () | method |
public static function directTreeWithRoot(tree:Graph, root:Node):EdgeList
Reverses some 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.
Precondition The given graph must be a tree.
Precondition The given node must be part of the given graph
Parameters
tree:Graph — the given tree.
| |
root:Node — the given root element.
|
EdgeList — an com.yworks.yfiles.base.EdgeList that contains the reversed edges.
|
See also
getCenterRoot | () | method |
public static function getCenterRoot(tree:Graph):Node
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.
Precondition !tree.isEmpty()
Precondition isTree(tree)
Parameters
tree:Graph — the given undirected tree.
|
Node — the center node of the given undirected tree.
|
getClass | () | method |
override public function getClass():Class
ReturnsClass |
getLeafNodes | () | method |
public static function getLeafNodes(tree:Graph, directedRootedTree:Boolean):NodeList
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:Graph — the given tree.
| |
directedRootedTree:Boolean — whether or not to consider the tree as directed rooted tree.
|
NodeList — a NodeList that contains all leaf nodes of the given tree.
|
getNearestCommonAncestor | () | method |
public static function getNearestCommonAncestor(tree:Graph, root:Node, rootedDownward:Boolean, nodes:NodeList):Node
Returns the nearest common ancestor of a subset of nodes within a directed rooted tree. It is not part of the given subset.
Precondition isTree(tree)
Complexity O(tree.N())
Parameters
tree:Graph — the given directed rooted tree.
| |
root:Node — the root of the tree.
| |
rootedDownward:Boolean — whether the tree is directed from the root to the leaves (true ) or from the leaves to the root (false ).
| |
nodes:NodeList — the subset of nodes.
|
Node — the nearest common ancestor of the given subset of nodes.
|
getRoot | () | method |
public static function getRoot(tree:Graph):Node
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. Otherwise, if the input is a tree, the method returns a maximum weight center node as defined in getWeightedCenterNode(). If the input is not a tree, the node with indegree == 0 (or outdegree == 0) is returned.
Precondition isTree(tree)
or there is exactly one node with indegree == 0 or there is exactly one node with outdegree == 0
Precondition !tree.isEmpty()
Parameters
tree:Graph — the given tree.
|
Node — a possible root for the given tree.
|
See also
getSubTreeDepths | () | method |
public static function getSubTreeDepths(tree:Graph, subtreeDepthMap:NodeMap):void
Returns for a rooted directed tree the depths of each of its subtrees.
Parameters
tree:Graph — a rooted directed tree graph.
| |
subtreeDepthMap:NodeMap — 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 com.yworks.yfiles.base.NodeMap.getInt().
|
See also
getSubTreeSizes | () | method |
public static function getSubTreeSizes(tree:Graph, subtreeSizeMap:NodeMap):void
Returns for a rooted directed tree the size (number of nodes) of each of its subtrees.
Parameters
tree:Graph — a rooted directed tree graph
| |
subtreeSizeMap:NodeMap — 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 com.yworks.yfiles.base.NodeMap.getInt().
|
See also
getTreeEdges | () | method |
public static function getTreeEdges(graph:Graph):Vector.<Object>
Returns an array of EdgeList objects each containing edges that belong to a maximal directed subtree of the given graph.
Parameters
graph:Graph — the given graph.
|
Vector.<Object> — an array of com.yworks.yfiles.base.EdgeList objects each containing edges that belong to a maximal directed subtree.
|
See also
getTreeEdgesForTreeNodes | () | method |
public static function getTreeEdgesForTreeNodes(graph:Graph, treeNodes:Vector.<Object>):Vector.<Object>
Same as getTreeEdges() but more efficient if the treeNodes where calculated before by getTreeNodes(). Furthermore, the method can also be applied to the result obtained by getUndirectedTreeNodes(). In this case the subtrees are considered to be undirected.
Parameters
graph:Graph — the given graph.
| |
treeNodes:Vector.<Object> — An array of com.yworks.yfiles.base.NodeList s formerly calculated by getTreeNodes().
|
Vector.<Object> — an array of com.yworks.yfiles.base.EdgeList objects each containing edges that belong to a maximal subtree.
|
See also
getTreeNodes | () | method |
public static function getTreeNodes(graph:Graph):Vector.<Object>
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 root's indegree is at least two.
Parameters
graph:Graph — the given graph.
|
Vector.<Object> — an array of com.yworks.yfiles.base.NodeList objects each containing nodes that belong to a maximal directed subtree.
|
See also
getUndirectedTreeNodes | () | method |
public static function getUndirectedTreeNodes(graph:Graph):Vector.<Object>
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:Graph — the given graph.
|
Vector.<Object> — an array of com.yworks.yfiles.base.NodeList objects each containing nodes that belong to a maximal undirected subtree.
|
See also
getWeightedCenterNode | () | method |
public static function getWeightedCenterNode(tree:Graph):Node
Finds a node which is used by the greatest number of all (undirected) paths interconnecting all nodes with each other.
Precondition The given graph must be a tree (may be undirected).
Precondition
Parameters
tree:Graph — the given tree.
|
Node — a node which is used by the greatest number of all undirected paths.
|
getWeightedCenterNodeWithWeights | () | method |
public static function getWeightedCenterNodeWithWeights(tree:Graph, intWeight:NodeMap):Node
Finds a node which is 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.
Precondition The given graph must be a tree (may be undirected).
Precondition
Parameters
tree:Graph — the given tree.
| |
intWeight:NodeMap — a com.yworks.yfiles.base.NodeMap that is used to store the number of paths per node.
|
Node — a node which is used by the greatest number of all undirected paths.
|
See also
isForest | () | method |
public static function isForest(g:Graph):Boolean
Checks whether the given graph is a forest, that is, a graph whose connected components are directed rooted trees.
Parameters
g:Graph — the given graph.
|
Boolean — true if the given graph is a forest. Otherwise, the method returns false .
|
isForest2 | () | method |
public static function isForest2(g:Graph, directedRootedTree:Boolean):Boolean
Checks whether 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. Note: isForest(graph, true) => isForest(graph, false)
.
Parameters
g:Graph — the given graph.
| |
directedRootedTree:Boolean — whether to check for directed rooted trees.
|
Boolean — true if the given graph is a forest. Otherwise, the method returns false .
|
isNaryTree | () | method |
public static function isNaryTree(g:Graph, n:int):Boolean
Checks whether the given graph is a directed rooted tree where each node has a maximum of n
children.
Parameters
g:Graph — the given graph.
| |
n:int — the allowed maximum of children.
|
Boolean — true if the given graph is a directed rooted tree where each node has a maximum of n children. Otherwise, the method returns false .
|
isRootedTree | () | method |
public static function isRootedTree(g:Graph):Boolean
Checks whether the given graph is a directed rooted tree.
Note: isRootedTree(graph) => isTree(graph)
.
Parameters
g:Graph — the given graph.
|
Boolean — true if the given graph is a directed rooted tree. Otherwise, the method returns false .
|
isTree | () | method |
public static function isTree(g:Graph):Boolean
Checks whether or not the given graph is an undirected tree.
Note: isRootedTree(graph) => isTree(graph)
.
Parameters
g:Graph — the given graph.
|
Boolean — true if the given graph is an undirected tree. Otherwise, the method returns false .
|