(Removed) Find minimal spanning tree in biograph object - MATLAB minspantree (biograph)

Syntax

[Tree, pred] = minspantree(BGObj) [Tree, pred] = minspantree(BGObj, R) [Tree, pred] = minspantree(..., 'Method', MethodValue, ...) [Tree, pred] = minspantree(..., 'Weights', WeightsValue, ...)

Arguments

`BGObj`	Biograph object created by `biograph` (object constructor).
`R`	Scalar between 1 and the number of nodes.

Description

[Tree, pred] = minspantree(BGObj) finds an acyclic subset of edges that connects all the nodes in the undirected graph represented by an N-by-N adjacency matrix extracted from a biograph object, BGObj, and for which the total weight is minimized. Weights of the edges are all nonzero entries in the lower triangle of the N-by-N sparse matrix. Output Tree is a spanning tree represented by a sparse matrix. Output pred is a vector containing the predecessor nodes of the minimal spanning tree (MST), with the root node indicated by 0. The root node defaults to the first node in the largest connected component. This computation requires an extra call to the graphconncomp function.

Note

The function ignores the direction of the edges in the Biograph object.

[Tree, pred] = minspantree(BGObj, R) sets the root of the minimal spanning tree to node R.

[Tree, pred] = minspantree(..., 'PropertyName', PropertyValue, ...) calls minspantree with optional properties that use property name/property value pairs. You can specify one or more properties in any order. Each PropertyName must be enclosed in single quotes and is case insensitive. These property name/property value pairs are as follows:

[Tree, pred] = minspantree(..., 'Method', MethodValue, ...) lets you specify the algorithm used to find the minimal spanning tree (MST). Choices are:

'Kruskal' — Grows the minimal spanning tree (MST) one edge at a time by finding an edge that connects two trees in a spreading forest of growing MSTs. Time complexity is O(E+X*log(N)), where X is the number of edges no longer than the longest edge in the MST, and N and E are the number of nodes and edges respectively.
'Prim' — Default algorithm. Grows the minimal spanning tree (MST) one edge at a time by adding a minimal edge that connects a node in the growing MST with any other node. Time complexity is O(E*log(N)), where N and E are the number of nodes and edges respectively.

Note

When the graph is unconnected, Prim's algorithm returns only the tree that contains R, while Kruskal's algorithm returns an MST for every component.

[Tree, pred] = minspantree(..., 'Weights', WeightsValue, ...) lets you specify custom weights for the edges. WeightsValue is a column vector having one entry for every nonzero value (edge) in the N-by-N sparse matrix. The order of the custom weights in the vector must match the order of the nonzero values in the N-by-N sparse matrix when it is traversed column-wise. By default, minspantree gets weight information from the nonzero entries in the N-by-N sparse matrix.

References

[1] Kruskal, J.B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society 7, 48-50.

[2] Prim, R. (1957). Shortest Connection Networks and Some Generalizations. Bell System Technical Journal 36, 1389-1401.

[3] Siek, J.G. Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).