Class ComplexityEvaluator

java.lang.Object
solvers.queueingnet.treeAlgorithms.ComplexityEvaluator
Direct Known Subclasses:
TCComplexityEvaluator, TMVAComplexityEvaluator
public abstract class ComplexityEvaluator extends Object
Abstract class representing complexity evaluator for calculating the complexity of a tree algorithm if it were to be run on a given tree representing a network.
Author:
Ben Homer, 2014.

  • Field Details

    • qnm

      protected QNModel qnm
      The queueing network model we are trying to solve.

    • ccu

      protected ClassCoverageUtils ccu
      The ClassCoverageUtils object used for calculating the class coverage at certain nodes in the planted tree.

    • stdComplexity

      protected ComplexityEvaluator.ComplexityBundle stdComplexity
      Complexity of running standard/sequential version of algorithm over specified model.

    • treeComplexity

      protected ComplexityEvaluator.ComplexityBundle treeComplexity
      Complexity of running tree version of algorithm over specified model, for a given tree.

    • sparcityOfDemandsMatrix

      protected double sparcityOfDemandsMatrix
      The sparsity of the network demand matrix.

    • perClassSparsityMeasure

      protected double[] perClassSparsityMeasure
      The per class mean sparsity.

    • fcfToPcRatio

      protected double fcfToPcRatio
      The ratio of fully covered classes to partially covered classes for a given tree.

  • Constructor Details

    • ComplexityEvaluator

      public ComplexityEvaluator(QNModel qnm, ClassCoverageUtils ccu)
      Constructor.
      Parameters:
      qnm - The queueing network model we are trying to solve.
      ccu - The ClassCoverageUtils object used for calculating the class coverage at certain nodes in the planted tree.

  • Method Details

    • treeHasAcceptableComplexity

      public abstract boolean treeHasAcceptableComplexity(Node root, PopulationVector pv)
      Determines if the tree algorithm for the specified tree has better complexity characteristics than the standard/sequential algorithm for the same network.
      Parameters:
      root - The root node of the tree to test.
      pv - The per class population vector of the network.
      Returns:
      A boolean indicating whether the tree has an acceptable expected complexity.

    • getStandardAlgorithmComplexity

      protected abstract ComplexityEvaluator.ComplexityBundle getStandardAlgorithmComplexity(PopulationVector pv)
      Gets the complexity of running standard/sequential algorithm over a network with the specified population vector.
      Parameters:
      pv - The network's population vector.
      Returns:
      A ComplexityBundle containing the expected time and space complexities.

    • getTreeComplexity

      protected ComplexityEvaluator.ComplexityBundle getTreeComplexity(Node node, PopulationVector pv)
      Gets the complexity of running the tree algorithm over the specified tree.
      Parameters:
      node - The tree root.
      pv - The per class population vector of the network.
      Returns:
      A ComplexityBundle containing the expected time and space complexities.

    • getTreeWithBestComplexity

      public int getTreeWithBestComplexity(Node[] roots, PopulationVector pv)
      Determines which tree from a list has the best complexity characteristics.
      Parameters:
      roots - The list of tree roots.
      pv - The population vector of the network.
      Returns:
      The index of the tree which has the best complexity characteristics.

    • getLeafNodeComplexity

      protected abstract ComplexityEvaluator.ComplexityBundle getLeafNodeComplexity(Node node, PopulationVector pv)
      Gets the complexity of a leaf node computation in the tree algorithm.
      Parameters:
      node - The leaf node.
      pv - The per class population vector of the network.
      Returns:
      A ComplexityBundle containing the expected time and space complexities.

    • getSubnetNodeComplexity

      protected abstract ComplexityEvaluator.ComplexityBundle getSubnetNodeComplexity(Node node, PopulationVector pv)
      Gets the complexity of a subnetwork node computation in the tree algorithm.
      Parameters:
      node - The subnetwork node.
      pv - The per class population vector of the network.
      Returns:
      A ComplexityBundle containing the expected time and space complexities.

    • printSummary

      protected abstract void printSummary()
      Prints a summary of the complexity evaluators calculations.

    • getMachineCapabilities

      public void getMachineCapabilities()
      Prints out information about machine's spec.

    • getSparcityOfDemandsMatrix

      protected double getSparcityOfDemandsMatrix()
      Calculates the sparsity of the network's demand matrix.
      Returns:
      The sparsity measure on scale from 0 to 1.

    • calculateFcsToPcsRatio

      protected double calculateFcsToPcsRatio(Node root)
      Gets the ratio of fully covered classes to partially covered classes in the network.
      Parameters:
      root - The root node.
      Returns:
      The ratio of FCF to PCS.

    • calculateNumberOfPcs

      protected int calculateNumberOfPcs(Node root)

    • getPerClassSparsityIndex

      protected double[] getPerClassSparsityIndex()