TreeAlgorithm

This class provides diverse algorithms and services for tree-structured graphs or subgraphs.

Inheritance Hierarchy

TreeAlgorithm

Remarks

Note: Methods of this class work with instances of Graph. To analyze IGraph instances that are directed trees use TreeAnalyzer instead.

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.

Type Details

yfiles module: algorithms
yfiles-umd modules: All layout modules, view-layout-bridge
Legacy UMD name: yfiles.algorithms.Trees

Static Methods

collectSubtree

(root: YNode, nodes: YNodeList)

Collects all nodes of the subtree starting with root.

Remarks

Note: This method works with instances of Graph. To retrieve a subtree of a directed tree in an IGraph use getSubtree instead.

Parameters

options - Object
A map of options to pass to the method.

root - YNode: the root of the subtree
nodes - YNodeList: the list that is filled with the nodes of the subtree

directTree

(tree: Graph, root?: YNode) : EdgeList

Converts the given tree to a directed rooted tree with the given node as root element by reversing some edges.

Remarks

A list of all reversed edges will be returned by this method.

Preconditions

The given graph must be a .
The given node must be part of the given graph.

Parameters

options - Object
A map of options to pass to the method.

tree - Graph: the given tree
root - YNode: the given root element

Returns

↪EdgeList: an EdgeList containing the reversed edges

getCenterRoot

(tree: Graph) : YNode

Returns the center node of an undirected tree.

Remarks

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 .
The given graph must be a .

Parameters

options - Object
A map of options to pass to the method.

tree - Graph: the given undirected tree

Returns

↪YNode: the center node of the given undirected tree

getLeafNodes

(tree: Graph, directedRootedTree: boolean) : YNodeList

Returns all leaf nodes of the given tree.

Remarks

Note: This method works with instances of Graph. To retrieve all leaf nodes of a directed tree in an IGraph use getLeafNodes instead.

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

options - Object
A map of options to pass to the method.

tree - Graph: the given tree
directedRootedTree - boolean: true if the algorithm should consider the tree as directed, false otherwise

Returns

↪YNodeList: a YNodeList that contains all leaf nodes of the given tree

getNearestCommonAncestor

(tree: Graph, root: YNode, rootedDownward: boolean, nodes: YNodeList) : YNode

Returns the nearest common ancestor of a subset of nodes within a directed rooted tree.

Remarks

Note: This method works with instances of Graph. To determine the nearest common ancestor of nodes in a directed tree in an IGraph use getNearestCommonAncestor instead.

It is not part of the given subset.

Complexity

O(tree.N())

Preconditions

The given graph must be a .

Parameters

options - Object
A map of options to pass to the method.

tree - Graph: the given directed rooted tree
root - YNode: the root of the tree
rootedDownward - boolean: true if the tree is directed from the root to the leaves, false otherwise
nodes - YNodeList: the subset of nodes

Returns

↪YNode: the nearest common ancestor of the given subset of nodes

getRoot

(tree: Graph) : YNode

Returns a possible root for the given (undirected) tree.

Remarks

Note: This method works with instances of Graph. To determine the root of a directed tree in an IGraph use getRoot instead.

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.
If the input is not a tree, a node with indegree == 0 (or outdegree == 0) is returned.

Preconditions

The given graph must be a , or there is exactly one node with indegree == 0, or there is exactly one node with outdegree == 0
The graph must be .

Parameters

options - Object
A map of options to pass to the method.

tree - Graph: the given tree

Returns

↪YNode: a possible root for the given tree

getSubTreeDepths

(tree: Graph, subtreeDepthMap: INodeMap)

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

Parameters

options - Object
A map of options to pass to the method.

tree - Graph

a rooted directed tree graph

subtreeDepthMap - INodeMap

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

Domain	YNode
Values	number	a non-negative value representing the depth of the subtree rooted at each node

getSubTreeSizes

(tree: Graph, subtreeSizeMap: INodeMap)

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

Parameters

options - Object
A map of options to pass to the method.

tree - Graph

a rooted directed tree graph

subtreeSizeMap - INodeMap

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

Domain	YNode
Values	number	a non-negative value representing the depth of the subtree rooted at each node

getTreeEdges

(graph: Graph, treeNodes?: YNodeList[]) : EdgeList

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

Remarks

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

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the given graph
treeNodes - YNodeList[]: an array of YNodeLists previously calculated by getTreeNodes

Returns

↪EdgeList[]: an array of EdgeList objects each containing edges that belong to a maximal subtree

getTreeNodes

(graph: Graph) : YNodeList

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

Remarks

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

options - Object
A map of options to pass to the method.

graph - Graph: the given graph

Returns

↪YNodeList[]: an array of YNodeList objects each containing nodes that belong to a maximal directed subtree

getUndirectedTreeNodes

(graph: Graph) : YNodeList

Returns an array of YNodeList objects each containing nodes that belong to a maximal undirected subtree of the given graph.

Remarks

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

options - Object
A map of options to pass to the method.

graph - Graph: the given graph

Returns

↪YNodeList[]: an array of YNodeList objects each containing nodes that belong to a maximal undirected subtree

getWeightedCenterNode

(tree: Graph, intWeight?: INodeMap) : YNode

Finds a node used by the greatest number of all (undirected) paths interconnecting all nodes with each other.

Remarks

The number of paths per node are stored in the given INodeMap.

Preconditions

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

Parameters

options - Object
A map of options to pass to the method.

tree - Graph

the given tree

intWeight - INodeMap

the INodeMap that holds the number of paths per node

Domain	YNode
Values	number	an value representing the number of paths of each node

Returns

↪YNode: a YNode used by the greatest number of all undirected paths

isForest

(graph: Graph) : boolean

Checks whether or not the given graph is a forest, that is, a graph whose connected components are directed rooted trees.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is a forest use isForest instead.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the given graph

Returns

↪boolean: true if the given graph is a forest, false otherwise

isForest

(graph: Graph, directedRootedTree: boolean) : boolean

Checks whether or not the given graph is a forest.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is a forest use isForest instead.

If directedRootedTree == true, each component has to be a directed rooted tree. Otherwise, each component has to be an undirected tree.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the given graph
directedRootedTree - boolean: true if the algorithm should check for directed rooted trees, false otherwise

Returns

↪boolean: true if the given graph is a forest, false otherwise

isForest(graph, true) => isForest(graph, false)

isNaryTree

(graph: Graph, n: number) : boolean

Checks whether or not the given graph is a directed rooted tree in which each node has a maximum of n children.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is an n-ary tree use isNaryTree instead.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the given graph
n - number: the allowed maximum of children

Returns

↪boolean: true if the given graph is a n-ary tree, false otherwise

isRootedTree

(graph: Graph) : boolean

Checks whether or not the given graph is a directed rooted tree.

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is a directed tree use isTree instead.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the given graph

Returns

↪boolean: true if the given graph is a directed rooted tree, false otherwise

isRootedTree(graph) => isTree(graph)

isTree

(graph: Graph) : boolean

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

Remarks

Note: This method works with instances of Graph. To determine whether an IGraph is a tree use isTree instead.

Parameters

options - Object
A map of options to pass to the method.

graph - Graph: the given graph

Returns

↪boolean: true if the given graph is an undirected tree, false otherwise

isRootedTree(graph) => isTree(graph).