Class TCComplexityEvaluator

java.lang.Object
solvers.queueingnet.treeAlgorithms.ComplexityEvaluator
solvers.queueingnet.treeAlgorithms.treeConvolution.TCComplexityEvaluator
public class TCComplexityEvaluator extends ComplexityEvaluator
Class responsible for evaluating the complexity of the tree convolution algorithm if it were to be run on a given tree representing a network.
Author:
Ben Homer, 2014.

  • Constructor Details

    • TCComplexityEvaluator

      public TCComplexityEvaluator(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 boolean treeHasAcceptableComplexity(Node root, PopulationVector pv)
      Determines if the tree convolution algorithm for the specified tree has better complexity characteristics than the standard/sequential algorithm for the same network.
      Specified by:
      treeHasAcceptableComplexity in class ComplexityEvaluator
      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.

    • getLeafNodeComplexity

      protected ComplexityEvaluator.ComplexityBundle getLeafNodeComplexity(Node n, PopulationVector popVec)
      Gets the complexity of a leaf node computation in the tree convolution algorithm. Implements equation (8) in Lam/Lien paper which gives time of convolution between 2 subnets in tree.
      Specified by:
      getLeafNodeComplexity in class ComplexityEvaluator
      Parameters:
      n - The leaf node.
      popVec - The per class population vector of the network.
      Returns:
      A ComplexityBundle containing the expected time and space complexities.

    • getSubnetNodeComplexity

      protected ComplexityEvaluator.ComplexityBundle getSubnetNodeComplexity(Node n, PopulationVector popVec)
      Gets the complexity of a subnetwork node computation in the tree convolution algorithm. Implements equation (8) in Lam/Lien paper which gives time of convolution between 2 subnets in tree.
      Specified by:
      getSubnetNodeComplexity in class ComplexityEvaluator
      Parameters:
      n - The subnetwork node.
      popVec - The per class population vector of the network.
      Returns:
      A ComplexityBundle containing the expected time and space complexities.

    • getStandardAlgorithmComplexity

      protected ComplexityEvaluator.ComplexityBundle getStandardAlgorithmComplexity(PopulationVector popVec)
      Gets the complexity of running standard convolution over a network with the specified population vector.
      Specified by:
      getStandardAlgorithmComplexity in class ComplexityEvaluator
      Parameters:
      popVec - The network's population vector.
      Returns:
      A ComplexityBundle containing the expected time and space complexities.

    • printSummary

      protected void printSummary()
      Prints a summary of the complexity evaluators calculations.
      Specified by:
      printSummary in class ComplexityEvaluator