Minimum Spanning Tree
PortfolioOptimisers.KruskalTree — Type
struct KruskalTree{__T_args, __T_kwargs} <: AbstractTreeTypeGrows the minimum spanning tree with the lightest edge that joins two components, one edge at a time.
KruskalTree selects Kruskal's algorithm for calc_mst, which calls Graphs.kruskal_mst.
Fields
args: Positional arguments for the spanning tree function. Every positional slot of those functions is a weight channel, soassert_tree_argsrefuses a matrix or a vector here. The weights come with the graph.
kwargs: Keyword arguments for the spanning tree function.assert_tree_argsrefusesminimize, becauseminimize = falseinverts the minimisation that defines the tree branch.
Constructors
KruskalTree(; args::Tuple = (), kwargs::NamedTuple = (;)) -> KruskalTreeKeywords correspond to the struct's fields.
Validation
- No entry of
argsis anAbstractMatrixor anAbstractVector, andkwargsholds nominimizekey. Each of those reaches a channel that re-weights or re-orients the graph that theNetworkEstimatorbuilt.
Examples
julia> KruskalTree()KruskalTree args ┼ Tuple{}: () kwargs ┴ @NamedTuple{}: NamedTuple()Related
References
- [131] J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7, 48–50 (1956). Page 49, Construction A.
PortfolioOptimisers.BoruvkaTree — Type
struct BoruvkaTree{__T_args, __T_kwargs} <: AbstractTreeTypeGrows the minimum spanning tree with one edge from every component to its lightest neighbour, in each round.
BoruvkaTree selects Boruvka's algorithm for calc_mst, which calls Graphs.boruvka_mst.
Fields
args: Positional arguments for the spanning tree function. Every positional slot of those functions is a weight channel, soassert_tree_argsrefuses a matrix or a vector here. The weights come with the graph.
kwargs: Keyword arguments for the spanning tree function.assert_tree_argsrefusesminimize, becauseminimize = falseinverts the minimisation that defines the tree branch.
Constructors
BoruvkaTree(; args::Tuple = (), kwargs::NamedTuple = (;)) -> BoruvkaTreeKeywords correspond to the struct's fields.
Validation
- No entry of
argsis anAbstractMatrixor anAbstractVector, andkwargsholds nominimizekey. Each of those reaches a channel that re-weights or re-orients the graph that theNetworkEstimatorbuilt.
Examples
julia> BoruvkaTree()BoruvkaTree args ┼ Tuple{}: () kwargs ┴ @NamedTuple{}: NamedTuple()Related
References
- [132] O. Borůvka. O jistém problému minimálním. Práce Moravské Přírodovědecké Společnosti 3, 37–58 (1926).
- [133] J. Nešetřil, E. Milková and H. Nešetřilová. Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history. Discrete Mathematics 233, 3–36 (2001). Section 2, for an English translation, and Section 4, for the step that joins each vertex to its nearest neighbour.
PortfolioOptimisers.PrimTree — Type
struct PrimTree{__T_args, __T_kwargs} <: AbstractTreeTypeGrows the minimum spanning tree outward from one first vertex.
PrimTree selects Prim's algorithm for calc_mst, which calls Graphs.prim_mst.
Construction B of [131], one year before [134], grows the tree from a fixed set of vertices. With one vertex in that set, it is the same algorithm.
Fields
args: Positional arguments for the spanning tree function. Every positional slot of those functions is a weight channel, soassert_tree_argsrefuses a matrix or a vector here. The weights come with the graph.
kwargs: Keyword arguments for the spanning tree function.assert_tree_argsrefusesminimize, becauseminimize = falseinverts the minimisation that defines the tree branch.
Constructors
PrimTree(; args::Tuple = (), kwargs::NamedTuple = (;)) -> PrimTreeKeywords correspond to the struct's fields.
Validation
- No entry of
argsis anAbstractMatrixor anAbstractVector, andkwargsholds nominimizekey. Each of those reaches a channel that re-weights or re-orients the graph that theNetworkEstimatorbuilt.
Examples
julia> PrimTree()PrimTree args ┼ Tuple{}: () kwargs ┴ @NamedTuple{}: NamedTuple()Related
References
- [134] R. C. Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal 36, 1389–1401 (1957). Pages 1391-1392, Principles 1 and 2, and the variant that grows a single fragment.
- [131] J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7, 48–50 (1956). Page 49, Construction B.
References
- [131]
- J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society 7, 48–50 (1956).
- [132]
- O. Borůvka. O jistém problému minimálním. Práce Moravské Přírodovědecké Společnosti 3, 37–58 (1926).
- [133]
- J. Nešetřil, E. Milková and H. Nešetřilová. Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history. Discrete Mathematics 233, 3–36 (2001).
- [134]
- R. C. Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal 36, 1389–1401 (1957).