Minimum Spanning Tree

struct KruskalTree{__T_args, __T_kwargs} <: AbstractTreeType

Grows the minimum spanning tree by taking the lightest edge that joins two components.

KruskalTree specifies the use of Kruskal's algorithm for constructing a minimum spanning tree from a graph.

Fields

• args: Positional arguments for the spanning tree function. Every positional slot those functions declare is a weight channel, so assert_tree_args refuses a matrix or a vector here: the weights arrive with the graph.

• kwargs: Keyword arguments for the spanning tree function. assert_tree_args refuses minimize, which would invert the minimisation the tree branch is defined by.

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 would re-weight or re-orient the graph the NetworkEstimator built.

Examples

julia> KruskalTree()KruskalTree    args ┼ Tuple{}: ()  kwargs ┴ @NamedTuple{}: NamedTuple()

Related

• AbstractTreeType
• Graphs.kruskal_mst

References

• [55] 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).

struct BoruvkaTree{__T_args, __T_kwargs} <: AbstractTreeType

Grows the minimum spanning tree by joining every component to its own lightest neighbour at once.

BoruvkaTree specifies the use of Boruvka's algorithm for constructing a minimum spanning tree from a graph.

Fields

• args: Positional arguments for the spanning tree function. Every positional slot those functions declare is a weight channel, so assert_tree_args refuses a matrix or a vector here: the weights arrive with the graph.

• kwargs: Keyword arguments for the spanning tree function. assert_tree_args refuses minimize, which would invert the minimisation the tree branch is defined by.

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 would re-weight or re-orient the graph the NetworkEstimator built.

Examples

julia> BoruvkaTree()BoruvkaTree    args ┼ Tuple{}: ()  kwargs ┴ @NamedTuple{}: NamedTuple()

Related

• AbstractTreeType
• Graphs.boruvka_mst

References

• [56] O. Borůvka. O jistém problému minimálním. Práce Moravské Přírodovědecké Společnosti 3, 37–58 (1926).

struct PrimTree{__T_args, __T_kwargs} <: AbstractTreeType

Grows the minimum spanning tree outward from a single starting vertex.

PrimTree specifies the use of Prim's algorithm for constructing a minimum spanning tree from a graph.

Fields

• args: Positional arguments for the spanning tree function. Every positional slot those functions declare is a weight channel, so assert_tree_args refuses a matrix or a vector here: the weights arrive with the graph.

• kwargs: Keyword arguments for the spanning tree function. assert_tree_args refuses minimize, which would invert the minimisation the tree branch is defined by.

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 would re-weight or re-orient the graph the NetworkEstimator built.

Examples

julia> PrimTree()PrimTree    args ┼ Tuple{}: ()  kwargs ┴ @NamedTuple{}: NamedTuple()

Related

• AbstractTreeType
• Graphs.prim_mst

References

• [57] R. C. Prim. Shortest connection networks and some generalizations. The Bell System Technical Journal 36, 1389–1401 (1957).