Minimum Spanning Tree

PortfolioOptimisers.KruskalTree — Type
struct KruskalTree{__T_args, __T_kwargs} <: AbstractTreeType

Grows 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, so assert_tree_args refuses a matrix or a vector here. The weights come with the graph.
  • kwargs: Keyword arguments for the spanning tree function. assert_tree_args refuses minimize, because minimize = false inverts the minimisation that defines the tree branch.

Constructors

KruskalTree(;    args::Tuple = (),    kwargs::NamedTuple = (;)) -> KruskalTree

Keywords correspond to the struct's fields.

Validation

  • No entry of args is an AbstractMatrix or an AbstractVector, and kwargs holds no minimize key. Each of those reaches a channel that re-weights or re-orients the graph that the NetworkEstimator built.

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.
source
PortfolioOptimisers.BoruvkaTree — Type
struct BoruvkaTree{__T_args, __T_kwargs} <: AbstractTreeType

Grows 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, so assert_tree_args refuses a matrix or a vector here. The weights come with the graph.
  • kwargs: Keyword arguments for the spanning tree function. assert_tree_args refuses minimize, because minimize = false inverts the minimisation that defines the tree branch.

Constructors

BoruvkaTree(;    args::Tuple = (),    kwargs::NamedTuple = (;)) -> BoruvkaTree

Keywords correspond to the struct's fields.

Validation

  • No entry of args is an AbstractMatrix or an AbstractVector, and kwargs holds no minimize key. Each of those reaches a channel that re-weights or re-orients the graph that the NetworkEstimator built.

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.
source
PortfolioOptimisers.PrimTree — Type
struct PrimTree{__T_args, __T_kwargs} <: AbstractTreeType

Grows 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, so assert_tree_args refuses a matrix or a vector here. The weights come with the graph.
  • kwargs: Keyword arguments for the spanning tree function. assert_tree_args refuses minimize, because minimize = false inverts the minimisation that defines the tree branch.

Constructors

PrimTree(;    args::Tuple = (),    kwargs::NamedTuple = (;)) -> PrimTree

Keywords correspond to the struct's fields.

Validation

  • No entry of args is an AbstractMatrix or an AbstractVector, and kwargs holds no minimize key. Each of those reaches a channel that re-weights or re-orients the graph that the NetworkEstimator built.

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.
source

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).