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
@PRODUCT@ 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 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
See Also
Constructors
Parameters
A map of options to pass to the method.
- customRootNode - ItemCollection<INode>
- The node that will be used as root of the directed rooted tree. This option either sets the value directly or recursively sets properties to the instance of 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 either sets the value directly or recursively sets properties to the instance of 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 either sets the value directly or recursively sets properties to the instance of 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
Given a tree structure, any node can become its root. However, it might be necessary to adjust the edge directions to get a directed tree. The algorithm computes the edges that would need to be reversed and stores them in reversedEdges. Result queries like, e.g., getParent, are then treating those edges as reversed, thus, providing a view of a directed tree structure rooted at the node specified with this property.
If multiple root nodes are provided, the first valid node is used.
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.nodes,
})
// 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',
},
})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 instanceof Arrow &&
edge.style.targetArrow.type === ArrowType.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 &&
Color.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.