Package org.drip.graph.decisiontree

Class ComplexityEstimate

java.lang.Object
org.drip.graph.decisiontree.ComplexityEstimate
public class ComplexityEstimate
extends java.lang.Object
ComplexityEstimate implements the Asymptotic Size O (n) Complexity Estimates for Decision Trees Generation and Validation. 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

    • ComplexityEstimate

      public ComplexityEstimate​(int vertexCount) throws java.lang.Exception
      ComplexityEstimate Constructor
      Parameters:
      vertexCount - Vertex Count
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • vertexCount

      public int vertexCount()
      Retrieve the Count of Vertexes
      Returns:
      Count of Vertexes

    • numberOfPossibleGraphs

      public double numberOfPossibleGraphs()
      Retrieve the Number of Possible Graphs given the Vertex Count
      Returns:
      Number of Possible Graphs

    • optimalDepth

      public double optimalDepth()
      Retrieve the Optimal Depth of the Decision Tree
      Returns:
      Optimal Depth of the Decision Tree

    • internalNodesUpperBound

      public double internalNodesUpperBound()
      Retrieve the Upper Bound on the Number of Internal DT Nodes
      Returns:
      Upper Bound on the Number of Internal DT Nodes

    • graphEdgeUpperBound

      public double graphEdgeUpperBound()
      Retrieve the Upper Bound on the Number of Edges per Graph
      Returns:
      Upper Bound on the Number of Edges per Graph

    • comparisonUpperBound

      public double comparisonUpperBound()
      Retrieve the Upper Bound on the Number of Decision Tree Comparisons
      Returns:
      Upper Bound on the Number of Decision Tree Comparisons

    • generatedCountUpperBound

      public double generatedCountUpperBound()
      Retrieve the Upper Bound on the Number of Generated Decision Trees
      Returns:
      Upper Bound on the Number of Generated Decision Trees

    • generationMetrics

      public GenerationComplexity generationMetrics()
      Compute the Decision Tree Generation Complexity Estimation Metrics
      Returns:
      Decision Tree Generation Complexity Estimation Metrics

    • edgeWeightPermutationsUpperBound

      public double edgeWeightPermutationsUpperBound()
      Retrieve the Upper Bound on the Number of Edge Weight Permutations
      Returns:
      Upper Bound on the Number of Edge Weight Permutations

    • mstRuntimeUpperBound

      public double mstRuntimeUpperBound()
      Retrieve the Upper Bound on the MST Algorithm Runtime
      Returns:
      Upper Bound on the MST Algorithm Runtime

    • permutationsCheckUpperBound

      public double permutationsCheckUpperBound()
      Retrieve the Upper Bound on the Time required to check all Permutations
      Returns:
      Upper Bound on the Time required to check all Permutations

    • optimalDTFinderUpperBound

      public double optimalDTFinderUpperBound()
      Retrieve the Upper Bound on the Time for finding the Optimal DT Finding Time
      Returns:
      Upper Bound on the Time for finding the Optimal DT Finding Time

    • validationMetrics

      public ValidationComplexity validationMetrics()
      Generate the Decision Tree Validation Metrics
      Returns:
      The Decision Tree Validation Metrics

    • metrics

      public ComplexityMetrics metrics()
      Generate the Complete Decision Tree Metrics
      Returns:
      The Complete Decision Tree Metrics