Package org.drip.graph.mst

Class CompleteRandomGraphEnsemble

java.lang.Object
org.drip.graph.mst.CompleteRandomGraphEnsemble
public class CompleteRandomGraphEnsemble
extends java.lang.Object
CompleteRandomGraphEnsemble implements the Ensemble of Complete Random Graphs. 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




Author:
Lakshmi Krishnamurthy

  • Constructor Details

    • CompleteRandomGraphEnsemble

      public CompleteRandomGraphEnsemble​(CompleteRandomGraph completeRandomGraph, OptimalSpanningForestGenerator minimumSpanningForestGenerator) throws java.lang.Exception
      CompleteRandomGraphEnsemble Constructor
      Parameters:
      completeRandomGraph - The Underlying Complete Random Graph
      minimumSpanningForestGenerator - The Minimum Spanning Forest Generator
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • Prim

      public static final CompleteRandomGraphEnsemble Prim​(CompleteRandomGraph completeRandomGraph)
      Construct the Prim based CompleteRandomGraphEnsemble
      Parameters:
      completeRandomGraph - The Complete Random Graph
      Returns:
      The CompleteRandomGraphEnsemble Instance

    • Kruskal

      public static final CompleteRandomGraphEnsemble Kruskal​(CompleteRandomGraph completeRandomGraph)
      Construct the Kruskal based CompleteRandomGraphEnsemble
      Parameters:
      completeRandomGraph - The Complete Random Graph
      Returns:
      The CompleteRandomGraphEnsemble Instance

    • ReverseDelete

      public static final CompleteRandomGraphEnsemble ReverseDelete​(CompleteRandomGraph completeRandomGraph)
      Construct the Reverse-Delete based CompleteRandomGraphEnsemble
      Parameters:
      completeRandomGraph - The Complete Random Graph
      Returns:
      The CompleteRandomGraphEnsemble Instance

    • Boruvka

      public static final CompleteRandomGraphEnsemble Boruvka​(CompleteRandomGraph completeRandomGraph)
      Construct the Boruvka based CompleteRandomGraphEnsemble
      Parameters:
      completeRandomGraph - The Complete Random Graph
      Returns:
      The CompleteRandomGraphEnsemble Instance

    • completeRandomGraph

      public CompleteRandomGraph completeRandomGraph()
      Retrieve the Underlying Complete Random Graph
      Returns:
      The Underlying Complete Random Graph

    • minimumSpanningForestGenerator

      public OptimalSpanningForestGenerator minimumSpanningForestGenerator()
      Retrieve the Minimum Spanning Forest Generator
      Returns:
      The Minimum Spanning Forest Generator

    • length

      public double length() throws java.lang.Exception
      Compute the Length of the Minimum Spanning Forest
      Returns:
      Length of the Minimum Spanning Forest
      Throws:
      java.lang.Exception - Thrown if the Length of the Minimum Spanning Forest cannot be calculated