Package org.drip.graph.decisiontree

Class GenerationComplexity

java.lang.Object
org.drip.graph.decisiontree.GenerationComplexity
public class GenerationComplexity
extends java.lang.Object
GenerationComplexity implements the Asymptotic Size Complexity O (n) for Decision Tree Generation. 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 Summary

    Constructors
    Constructor Description
    GenerationComplexity​(double numberOfPossibleGraphs, double optimalDepth, double internalNodesUpperBound, double graphEdgeUpperBound, double comparisonUpperBound, double generationCountUpperBound)
    GenerationComplexity Constructor

  • Method Summary

    Modifier and Type Method Description
    double comparisonUpperBound()
    Retrieve the Upper Bound on the Number of Decision Tree Comparisons
    double generationCountUpperBound()
    Retrieve the Upper Bound on the Number of Generated Decision Trees
    double graphEdgeUpperBound()
    Retrieve the Upper Bound on the Number of Edges per Graph
    double internalNodesUpperBound()
    Retrieve the Upper Bound on the Number of Internal DT Nodes
    double numberOfPossibleGraphs()
    Retrieve the Number of Possible Graphs
    double optimalDepth()
    Retrieve the Optimal Depth of the Decision Tree

    Methods inherited from class java.lang.Object

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

  • Constructor Details

    • GenerationComplexity

      public GenerationComplexity​(double numberOfPossibleGraphs, double optimalDepth, double internalNodesUpperBound, double graphEdgeUpperBound, double comparisonUpperBound, double generationCountUpperBound) throws java.lang.Exception
      GenerationComplexity Constructor
      Parameters:
      numberOfPossibleGraphs - Number of Possible Graphs
      optimalDepth - Optimal Depth of the Decision Tree
      internalNodesUpperBound - Upper Bound on the Number of Internal DT Nodes
      graphEdgeUpperBound - Upper Bound on the Number of Edges per Graph
      comparisonUpperBound - Upper Bound on the Number of Decision Tree Comparisons
      generationCountUpperBound - Upper Bound on the Number of Generated Decision Trees
      Throws:
      java.lang.Exception - Thrown if the Inputs are Invalid

  • Method Details

    • numberOfPossibleGraphs

      public double numberOfPossibleGraphs()
      Retrieve the Number of Possible Graphs
      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

    • generationCountUpperBound

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