Package org.drip.graph.mst

Class CompleteRandomGraph

java.lang.Object

org.drip.graph.core.Network

org.drip.graph.core.DirectedGraph

org.drip.graph.mst.CompleteRandomGraph

public class CompleteRandomGraph
extends DirectedGraph

CompleteRandomGraph implements the Expected Size Metrics for a Complete Graph with Randomly Distributed Weights and non-zero Count 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
CompleteRandomGraph(int vertexCount, RandomNumberGenerator randomNumberGenerator)	CompleteRandomGraph Constructor

Method Summary

Modifier and Type	Method	Description
RandomNumberGenerator	randomNumberGenerator()	Retrieve the Random Number Generator
static CompleteRandomGraph	Uniform(int vertexCount)	Compute a Uniform Instance of the Complete Random Graph

Methods inherited from class org.drip.graph.core.DirectedGraph

addGraph, areVertexesAdjacent, clone, containsCycle, fundamentalCycleEdgeSet, isComplete, isConnected, isCyclical, isDense, isTree, isTreeSpanning, kirchoffSpanningTreeCount, leafVertexNameList, spanningTreeCount, Transpose, type, vertexDegreeMap

Methods inherited from class org.drip.graph.core.Network

addBidirectionalEdge, addEdge, addVertex, containsEdge, containsVertex, edgeCount, edgeMap, edgePriorityQueue, initialVertexName, isEdgeACycle, isEmpty, length, removeEdge, vertexCount, vertexMap, vertexNameSet

Methods inherited from class java.lang.Object

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

Constructor Details

CompleteRandomGraph

public CompleteRandomGraph(int vertexCount,
RandomNumberGenerator randomNumberGenerator)
                    throws java.lang.Exception

CompleteRandomGraph Constructor

Parameters:

vertexCount - Count of Vertexes

randomNumberGenerator - Random Number Generator

Throws:

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

Method Details

Uniform

public static final CompleteRandomGraph Uniform(int vertexCount)

Compute a Uniform Instance of the Complete Random Graph

Parameters:

vertexCount - Count of Vertexes

Returns:

Uniform Instance of the Complete Random Graph

randomNumberGenerator

public RandomNumberGenerator randomNumberGenerator()

Retrieve the Random Number Generator

Returns:

The Random Number Generator