C

SpanningTree

Show Usages
Calculates a minimum spanning tree or forest for a graph.
Inheritance Hierarchy

Remarks

Definitions

  • A spanning tree of an undirected connected graph is a subset of its edges that induce a tree that connects all nodes of the graph.
  • A minimum spanning tree of a weighted connected graph is a spanning tree whose edges have minimum overall cost among all spanning trees of that graph.

If the graph is not connected, the result is a (minimum) spanning forest instead, whose components are spanning trees.

Other Tree-Related Algorithms

yFiles for HTML supports a number of other algorithms and helpers related to trees:

  • FeedbackEdgeSet – finds edges that can be removed or reversed to make a graph into a tree
  • TreeAnalysis – analyzes directed trees and provides access to tree properties, for example, the root node, the set of leaf nodes or the depth of a node.

Complexity

  • O(|V| + |E|) for graphs with uniform-cost edges
  • O(|E| ⋅ log(|V|)) otherwise

Examples

Calculating a spanning tree of the graph
// prepare the spanning tree detection algorithm
const algorithm = new SpanningTree()
// run the algorithm
const result = algorithm.run(graph)

// Remove the edges in the reduction
for (const edge of result.edges) {
  graph.setStyle(edge, spanningTreeEdgeStyle)
}

See Also

Developer's Guide

API

minimumSpanningTree

Members

No filters for this type

Constructors

SpanningTree

()

Parameters

Properties

costs

: ItemMapping<IEdge, number>
Gets or sets a mapping for edge costs.
When specifying costs, the algorithm will minimize the total cost of edges that form the spanning tree.
conversionfinal

See Also

Developer's Guide

subgraphEdges

: ItemCollection<IEdge>
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 ItemCollection<TItem>.excludes are set, all edges in the graph except those provided in the ItemCollection<TItem>.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.

The edges provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Calculating a spanning tree of a subset of the graph
// prepare the spanning tree detection algorithm
const algorithm = new SpanningTree({
  // 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)

// Remove the edges in the reduction
for (const edge of result.edges) {
  graph.setStyle(edge, spanningTreeEdgeStyle)
}

subgraphNodes

: ItemCollection<INode>
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 ItemCollection<TItem>.excludes are set, all nodes in the graph except those provided in the ItemCollection<TItem>.excludes are processed.

ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.

The nodes provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Calculating a spanning tree of a subset of the graph
// prepare the spanning tree detection algorithm
const algorithm = new SpanningTree({
  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)

// Remove the edges in the reduction
for (const edge of result.edges) {
  graph.setStyle(edge, spanningTreeEdgeStyle)
}

Methods

run

(graph: IGraph): SpanningTreeResult
Calculates a minimum spanning tree or forest for the given graph.
The result obtained from this algorithm is a snapshot which is no longer valid once the graph has changed, e.g. by adding or removing nodes or edges.
final

Parameters

graph: IGraph
The input graph to run the algorithm on.

Return Value

SpanningTreeResult
A SpanningTreeResult containing the edges that make up the spanning tree (or forest).

Throws

Exception ({ name: 'InvalidOperationError' })
If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.

Complexity

  • O(|V| + |E|) for graphs with uniform-cost edges
  • O(|E| ⋅ log(|V|)) otherwise