Minimum Spanning Tree: private API

abstract type AbstractTreeType <: AbstractPhylogenyAlgorithm

Abstract supertype for all minimum spanning tree (MST) algorithm types.

All concrete and/or abstract types implementing specific MST algorithms (e.g., Kruskal, Boruvka, Prim) should be subtypes of AbstractTreeType.

Related

• KruskalTree
• BoruvkaTree
• PrimTree

References

• [5] D. Cajas. Advanced Portfolio Optimization: A Cutting-edge Quantitative Approach (Springer Nature Switzerland, 2025). Section 13.1.4.1.
• [58] R. N. Mantegna. Hierarchical structure in financial markets. The European Physical Journal B 11, 193–197 (1999).

const Tree_SimMat = Union{<:AbstractNonNegativeSimilarityMatrixAlgorithm,
                          <:AbstractTreeType}

Alias for a tree or similarity matrix algorithm.

Matches either an AbstractNonNegativeSimilarityMatrixAlgorithm or an AbstractTreeType. Used for dispatch in phylogeny estimation where either a spanning tree or a similarity matrix approach may be used.

The similarity half is the narrow family, not AbstractSimilarityMatrixAlgorithm: the similarity branch builds a PMFG, whose consumers cannot take a negative weight. So MaximumDistanceSimilarity, ExponentialSimilarity, GeneralExponentialSimilarity and ComplementSimilarity match, and AngularSimilarity does not.

Related

• AbstractNonNegativeSimilarityMatrixAlgorithm
• AbstractSimilarityMatrixAlgorithm
• AbstractTreeType
• NetworkEstimator

calc_mst(alg::AbstractTreeType, g::Graphs.AbstractGraph)

Compute the minimum spanning tree (MST) of a graph using the specified algorithm.

This function dispatches to the appropriate MST computation from Graphs.jl based on the type of alg. Supported algorithms include Kruskal, Boruvka, and Prim.

Algorithm

1. Select the Graphs.jl spanning-tree routine that the type of alg names.
2. Splat alg.args and alg.kwargs into that call. assert_tree_args refused every entry that could re-weight or re-orient the search, so the tree is minimised over the weights g already carries.
3. Read the edge vector out of the answer. Graphs.boruvka_mst answers with a named tuple whose first field holds it, and the other two routines answer with the vector itself.

Arguments

• alg: MST algorithm to use.

  • alg::KruskalTree: Computes the MST using Kruskal's algorithm.
  • alg::BoruvkaTree: Computes the MST using Boruvka's algorithm.
  • alg::PrimTree: Computes the MST using Prim's algorithm.

• g::Graphs.AbstractGraph: Graph to compute the MST on.

Returns

• tree::Vector: Vector of edges representing the MST.

Related

• KruskalTree
• BoruvkaTree
• PrimTree