Analyzes a tree graph and calculates important properties of the tree structure.
Remarks
The algorithm supports directed, rooted trees as well as undirected tree structures. Property directedRootedTree yields whether or not the input is a directed, rooted tree.
Note that if it is only required to check whether a graph is a tree/rooted tree while no other tree information is needed, then the utility method isTree offered by GraphStructureAnalyzer is recommended instead.
For undirected trees, this algorithm computes a set of reversedEdges that would need to be reversed in order to make it a directed tree. The TreeAnalysisResult, thus, always yields a directed view of the structure when rooted at node root. Property customRootNode allows to get the analysis result when directing the tree structure such that the specified custom node is the root of the tree.
Other Tree-Related Algorithms
yFiles for HTML supports a number of other algorithms related to trees:
- FeedbackEdgeSet – finds edges that can be removed or reversed to convert a graph into a tree
- SpanningTree – calculates a (minimum) spanning tree for a graph
Examples
// create the tree analysis algorithm
const treeAnalysis = new TreeAnalysis()
// run the analysis
const result = treeAnalysis.run(graph)
// query the root node
const treeRoot = result.root
// query the child nodes of the root and set a specific tag for them
result.getChildren(treeRoot).forEach((node) => (node.tag = 'RootChild'))
// query the nearest common ancestor of two nodes
const nearestCommonAncestor = result.getNearestCommonAncestor(
node1,
node2
)// create the tree analysis algorithm
const treeAnalysis = new TreeAnalysis()
// run the analysis
const result = treeAnalysis.run(graph)
// query the root node
const treeRoot = result.root!
// query the child nodes of the root and set a specific tag for them
result.getChildren(treeRoot).forEach((node) => (node.tag = 'RootChild'))
// query the nearest common ancestor of two nodes
const nearestCommonAncestor = result.getNearestCommonAncestor(
node1,
node2
)// create and run the analysis
const result = new TreeAnalysis().run(graph)
if (!result.directedRootedTree) {
// if the tree is not already a directed rooted tree
result.reversedEdges.forEach((edge) => {
// reverse edges that the analysis found need reversal in order to get a directed tree
graph.reverse(edge)
// set a specific style to highlight edges that have been reversed
graph.setStyle(edge, highlightReversedEdgesStyle)
})
}Type Details
- yfiles module
- view-layout-bridge
- yfiles-umd modules
- view-layout-bridge
- Legacy UMD name
- yfiles.analysis.TreeAnalysis
See Also
Constructors
Creates a new instance of this class.
Parameters
A map of options to pass to the method.
- customRootNode - SingleItem<INode>
The node that will be used as root of the directed rooted tree. This option sets the customRootNode property on the created object.
- subgraphNodes - ItemCollection<INode>
The collection of nodes which define a subset of the graph for the algorithms to work on. This option sets the subgraphNodes property on the created object.
- subgraphEdges - ItemCollection<IEdge>
The collection of edges which define a subset of the graph for the algorithms to work on. This option sets the subgraphEdges property on the created object.
Properties
Gets or sets the node that will be used as root of the directed rooted tree.
Remarks
Examples
// explicitly set custom root as Item
analysis = new TreeAnalysis({
customRootNode: myRoot
})
// the custom root is the first item in the Source (the first selected node)
analysis = new TreeAnalysis({
customRootNode: graphComponent.selection.selectedNodes
})
// the custom root is the first in the graph for which the predicate returns true
// (the first node in the graph with "Root" as tag)
analysis = new TreeAnalysis({
customRootNode: {
delegate: (node) => node.tag === 'Root'
}
})See Also
Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.
Remarks
If nothing is set, all edges of the graph will be processed.
If only the excludes are set all edges in the graph except those provided in the excludes are processed.
Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered by the algorithm.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// create the tree analysis algorithm
const algorithm = new TreeAnalysis({
// ignore edges without target arrow heads
subgraphEdges: {
excludes: {
delegate: (edge) =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow === IArrow.NONE
}
}
})
// run the algorithm asynchronously
const result = algorithm.run(graph)Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.
Remarks
If nothing is set, all nodes of the graph will be processed.
If only the excludes are set all nodes in the graph except those provided in the excludes are processed.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// create the tree analysis algorithm
const algorithm = new TreeAnalysis({
// only consider green nodes in the graph
subgraphNodes: {
delegate: (node) =>
node.style instanceof ShapeNodeStyle &&
Fill.GREEN.hasSameValue(node.style.fill),
// but ignore the first node, regardless of its color
excludes: graph.nodes.first()
}
})
// run the algorithm asynchronously
const result = algorithm.run(graph)Methods
Analyzes a tree graph and calculates relevant properties of the tree structure.
Complexity
O(|V|)
Parameters
A map of options to pass to the method.
- graph - IGraph
- The input tree graph to run the algorithm on.
Returns
- ↪TreeAnalysisResult
- A TreeAnalysisResult allowing to query tree properties like the parent of a node or the tree root.
Throws
- Exception({ name: 'InvalidOperationError' })
- If the graph is not a tree or due to wrongly configured properties.