Remarks
The root of a tree is the only node which may have non-tree edges. Furthermore, a tree only consists of elements with the same nodeTypes.
The edgeDirectedness is considered as follows: A substructure is only identified as such if all edges are either undirected or consistently directed with respect to the specified directedness.
- A directedness value of
1indicates that the edge is considered to be directed from source to target. - A directedness value of
-1indicates that the edge is considered to be directed from target to source. - A directedness value of
0indicates that the edge is considered to be undirected.
Examples
// prepare the tree detection algorithm
const algorithm = new TreeSubstructures()
// run the algorithm
const result = algorithm.run(graph)
// highlight the trees
for (const tree of result.trees) {
for (const node of tree.nodes) {
graph.setStyle(node, highlightNodeStyle)
}
for (const edge of tree.edges) {
graph.setStyle(edge, highlightEdgeStyle)
}
}// prepare the tree detection algorithm
const algorithm = new TreeSubstructures({
// only nodes with the same tags can be a tree
nodeTypes: (node: INode): any => node.tag,
})
// run the algorithm
const result = algorithm.run(graph)
// highlight the trees
for (const tree of result.trees) {
for (const node of tree.nodes) {
graph.setStyle(node, highlightNodeStyle)
}
for (const edge of tree.edges) {
graph.setStyle(edge, highlightEdgeStyle)
}
}See Also
Developer's Guide
Members
Constructors
Properties
Gets or sets a mapping that stores the directedness of the edges.
- the edge's directedness is greater than
0.0and the edge is incoming (i.e. n is the edge's target), - the edge's directedness is smaller than
0.0and the edge is outgoing (i.e. n is the edge's source), - or the edge's directedness is
0.0(i.e. the edge is considered to be undirected).
Trees with fewer nodes are ignored.
Default is 3.
3.Gets or sets a mapping which maps the type of each node.
An arbitrary object. Nodes returning equal objects are considered to be of the same type.
If none is provided, all nodes are considered as equal.
Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.
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
// prepare the tree detection algorithm
const algorithm = new TreeSubstructures({
// Ignore edges without target arrow heads
subgraphEdges: {
excludes: (edge: IEdge): boolean =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow instanceof Arrow &&
edge.style.targetArrow.type === ArrowType.NONE,
},
})
// run the algorithm
const result = algorithm.run(graph)
// highlight the trees
for (const tree of result.trees) {
for (const node of tree.nodes) {
graph.setStyle(node, highlightNodeStyle)
}
for (const edge of tree.edges) {
graph.setStyle(edge, highlightEdgeStyle)
}
}Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.
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
// prepare the tree detection algorithm
const algorithm = new TreeSubstructures({
subgraphNodes: {
// only consider elliptical nodes in the graph
includes: (node: INode): boolean =>
node.style instanceof ShapeNodeStyle &&
node.style.shape === ShapeNodeShape.ELLIPSE,
// but ignore the first node, regardless of its shape
excludes: graph.nodes.first()!,
},
})
// run the algorithm
const result = algorithm.run(graph)
// highlight the trees
for (const tree of result.trees) {
for (const node of tree.nodes) {
graph.setStyle(node, highlightNodeStyle)
}
for (const edge of tree.edges) {
graph.setStyle(edge, highlightEdgeStyle)
}
}Methods
Returns a list of SubstructureItems that represent isolated trees in the specified graph.
The root of a tree is the only node which may have non-tree edges. Furthermore, a tree only consists of elements with the same nodeTypes.
The edgeDirectedness is considered as follows: A substructure is only identified as such if all edges are either undirected or consistently directed with respect to the specified directedness.
- A directedness value of
1indicates that the edge is considered to be directed from source to target. - A directedness value of
-1indicates that the edge is considered to be directed from target to source. - A directedness value of
0indicates that the edge is considered to be undirected.
3.Parameters
- graph: IGraph
- The graph to find the substructures in.
Return Value
- TreeSubstructuresResult
- A list of SubstructureItems that represent the trees.
Throws
- Exception ({ name: 'InvalidOperationError' })
- If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.
Examples
// prepare the tree detection algorithm
const algorithm = new TreeSubstructures()
// run the algorithm
const result = algorithm.run(graph)
// highlight the trees
for (const tree of result.trees) {
for (const node of tree.nodes) {
graph.setStyle(node, highlightNodeStyle)
}
for (const edge of tree.edges) {
graph.setStyle(edge, highlightEdgeStyle)
}
}// prepare the tree detection algorithm
const algorithm = new TreeSubstructures({
// only nodes with the same tags can be a tree
nodeTypes: (node: INode): any => node.tag,
})
// run the algorithm
const result = algorithm.run(graph)
// highlight the trees
for (const tree of result.trees) {
for (const node of tree.nodes) {
graph.setStyle(node, highlightNodeStyle)
}
for (const edge of tree.edges) {
graph.setStyle(edge, highlightEdgeStyle)
}
}