This class provides (minimum) spanning tree algorithms for graphs.
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.
Type Details
- yfiles module
- algorithms
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.algorithms.SpanningTrees
Static Methods
Returns the overall cost of a previously calculated minimum spanning tree.
Parameters
A map of options to pass to the method.
- treeEdges - EdgeList
- the given list of edges that form a minimum spanning tree
- edgeCost - IDataProvider
- the IDataProvider that returns a double value (cost) for each tree edge
Domain Edge a tree Values number a value that represents the cost of each tree edge
Returns
- ↪number
- the overall cost of the tree edges
Calculates a minimum spanning tree for the given graph.
Remarks
Note: This method works with instances of Graph. To find a minimum spanning tree for an IGraph use SpanningTree instead.
The implementation is based on an algorithm originally published in:
- J.B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, pages 48-50, 1956.
Complexity
graph.E() + graph.N() * log(graph.N())
Preconditions
- The graph must be
. cost.length == graph.E()
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- cost - IDataProvider
- the IDataProvider that returns a double value (cost) for each edge
Domain Edge Values number a value that represents the cost of each edge
Returns
Calculates a minimum spanning tree for the given graph.
Remarks
Note: This method works with instances of Graph. To find a minimum spanning tree for an IGraph use SpanningTree instead.
Currently, the result is obtained by calling prim.
Complexity
graph.E() * log(graph.N())
Preconditions
- The graph must be
. cost.length == graph.E()
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- cost - IDataProvider
- the IDataProvider that returns a double value (cost) for each edge
Domain Edge Values number a value that represents the cost of each edge
Returns
Calculates a minimum spanning tree for the given graph.
Remarks
Note: This method works with instances of Graph. To find a minimum spanning tree for an IGraph use SpanningTree instead.
The implementation is based on an algorithm originally published in:
- R.C. Prim. Shortest connection networks and some generalizations. Bell System Technical Journal, 36:1389-1401, 1957.
Complexity
graph.E() * log(graph.N())
Preconditions
- The graph must be
. cost.length == graph.E()
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- cost - IDataProvider
- the IDataProvider that returns a double value (cost) for each edge
Domain Edge Values number a value that represents the cost of each edge
Returns
Calculates a spanning tree for the given graph in which each edge has a uniform cost of 1.0.
Remarks
Complexity
O(graph.E() + graph.N())
Preconditions
- The graph must be
.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph