Package org.drip.graph.mst

Class SteeleCompleteUniformRandomTree

java.lang.Object

org.drip.graph.mst.SteeleCompleteUniformRandomTree

public class SteeleCompleteUniformRandomTree
extends java.lang.Object

SteeleCompleteUniformRandomTree holds the Expected Length of the MST computed by Steele (2002) for Graphs with small Number of Vertexes. The References are:

• Bader, D. A., and G. Cong (2006): Fast Shared Memory Algorithms for computing the Minimum Spanning Forests of Sparse Graphs Journal of Parallel and Distributed Computing 66 (11) 1366-1378
• Chazelle, B. (2000): A Minimum Spanning Tree Algorithm with Inverse-Ackerman Type Complexity Journal of the Association for Computing Machinery 47 (6) 1028-1047
• Karger, D. R., P. N. Klein, and R. E. Tarjan (1995): A Randomized Linear-Time Algorithm to find Minimum Spanning Trees Journal of the Association for Computing Machinery 42 (2) 321-328
• Pettie, S., and V. Ramachandran (2002): An Optimal Minimum Spanning Tree Algorithm Journal of the ACM 49 (1) 16-34
• Wikipedia (2020): Minimum Spanning Tree https://en.wikipedia.org/wiki/Minimum_spanning_tree

• Module = Computational Core Module
• Library = Graph Algorithm Library
• Project = Graph Optimization and Tree Construction Algorithms
• Package = Agnostic Minimum Spanning Tree Properties

Author:

Lakshmi Krishnamurthy

Constructor Summary

Constructors

Constructor	Description
SteeleCompleteUniformRandomTree()

Method Summary

Modifier and Type	Method	Description
static double	AsymptoticFriezeMSTLength()	Compute the Length of the MST for Large n (attribution to Alan M.
static double	AsymptoticFriezeMSTLength(R1Univariate r1Univariate)	Compute the Length of the MST for Large n (attribution to Alan M.
static boolean	ContainsVertexCount(int vertexCount)	Indicate if the Vertex Count is present in the Vertex Count Map
static boolean	Init()	Initialize the Steele Vertex MST Map
static SteeleCompleteUniformRandomEntry	VertexCountEntry(int vertexCount)	Retrieve the Vertex Count Entry if present in the Vertex Count Map
static java.util.Map<java.lang.Integer,SteeleCompleteUniformRandomEntry>	VertexCountMap()	Retrieve the Steele Vertex Count Map

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

SteeleCompleteUniformRandomTree

public SteeleCompleteUniformRandomTree()

Method Details

Init

public static final boolean Init()

Initialize the Steele Vertex MST Map

Returns:

TRUE - The Steele Vertex MST Map successfully initialized

VertexCountMap

public static final java.util.Map<java.lang.Integer,SteeleCompleteUniformRandomEntry> VertexCountMap()

Retrieve the Steele Vertex Count Map

Returns:

Steele Vertex Count Map

ContainsVertexCount

public static final boolean ContainsVertexCount(int vertexCount)

Indicate if the Vertex Count is present in the Vertex Count Map

Parameters:

vertexCount - Vertex Count

Returns:

TRUE - The Vertex Count is present in the Vertex Count Map

VertexCountEntry

public static final SteeleCompleteUniformRandomEntry VertexCountEntry(int vertexCount)

Retrieve the Vertex Count Entry if present in the Vertex Count Map

Parameters:

vertexCount - Vertex Count

Returns:

TRUE - The Vertex Count Entry

AsymptoticFriezeMSTLength

public static final double AsymptoticFriezeMSTLength()

Compute the Length of the MST for Large n (attribution to Alan M. Frieze)

Returns:

Length of the MST for Large n

AsymptoticFriezeMSTLength

public static final double AsymptoticFriezeMSTLength(R1Univariate r1Univariate)
                                              throws java.lang.Exception

Compute the Length of the MST for Large n (attribution to Alan M. Frieze)

Parameters:

r1Univariate - The R¹ Univariate Distribution of the Weights

Returns:

Length of the MST for Large n

Throws:

java.lang.Exception - Thrown if the Inputs are Invalid