Minimum Spanning Tree: private API

PortfolioOptimisers.AbstractTreeType — Type
abstract type AbstractTreeType <: AbstractPhylogenyAlgorithm

Abstract supertype for the algorithms that build a minimum spanning tree.

Every concrete or abstract type that selects a minimum spanning tree algorithm must subtype AbstractTreeType. A subtype goes in the alg field of a NetworkEstimator, and calc_mst runs the algorithm that it selects.

Related

References

  • [135] R. N. Mantegna. Hierarchical structure in financial markets. The European Physical Journal B 11, 193–197 (1999). Page 194, for the minimum spanning tree of the distances of Equation 2.
source
PortfolioOptimisers.Tree_SimMat — Type
const Tree_SimMat = Union{AbstractNonNegativeSimilarityMatrixAlgorithm,
                          AbstractTreeType}

Union of the tree algorithms and the non-negative similarity algorithms.

It is the bound of the alg field of a NetworkEstimator, and of the alg argument of calc_weighted_adjacency. A tree algorithm selects a minimum spanning tree, and a similarity algorithm selects a PMFG.

The similarity members come from AbstractNonNegativeSimilarityMatrixAlgorithm, and not from the wider AbstractSimilarityMatrixAlgorithm. The similarity branch builds a PMFG, and the consumers of a PMFG cannot take a negative weight. MaximumDistanceSimilarity, ExponentialSimilarity, GeneralExponentialSimilarity and ComplementSimilarity are members, and AngularSimilarity is not.

Related

source
PortfolioOptimisers.calc_mst — Function
calc_mst(alg::AbstractTreeType, g::Graphs.AbstractGraph)

Compute the minimum spanning tree of a graph with the algorithm that alg selects.

The type of alg selects one of three routines of Graphs.jl.

Algorithm

  1. Select the spanning tree routine of Graphs.jl that the type of alg names.
  2. Splat alg.args and alg.kwargs into that call. The constructor of alg called assert_tree_args, which refuses every entry that can re-weight or re-orient the search. The routine then minimises the tree over the weights that g carries.
  3. Return the vector of edges. Graphs.boruvka_mst returns a named tuple whose first field holds the vector, and the other two routines return the vector.

Arguments

  • alg: Minimum spanning tree algorithm.

    • alg::KruskalTree: Kruskal's algorithm, through Graphs.kruskal_mst.
    • alg::BoruvkaTree: Boruvka's algorithm, through Graphs.boruvka_mst.
    • alg::PrimTree: Prim's algorithm, through Graphs.prim_mst.
  • g::Graphs.AbstractGraph: Weighted graph to span.

Returns

  • tree::Vector: Edges of the minimum spanning tree.

Related

source

References

[135]
R. N. Mantegna. Hierarchical structure in financial markets. The European Physical Journal B 11, 193–197 (1999).