ptolemy.graph.analysis.strategy
Class ParhiMaximumProfitToCostRatioStrategy

java.lang.Object
  ptolemy.graph.analysis.strategy.Strategy
      ptolemy.graph.analysis.strategy.CachedStrategy
          ptolemy.graph.analysis.strategy.ParhiMaximumProfitToCostRatioStrategy

All Implemented Interfaces:

Analyzer, GraphAnalyzer, MaximumProfitToCostRatioAnalyzer

public class ParhiMaximumProfitToCostRatioStrategy
extends CachedStrategy
implements MaximumProfitToCostRatioAnalyzer

Maximum profit to cost ratio analyzer which uses Parhi's algorithm for iteration bound.

For details about the algorithm, please refer to:

K. Ito and K. K. Parhi. Determining the minimum iteration period of an algorithm. Journal of VLSI Signal Processing, 11(3):229-244, December 1995

Since:

Ptolemy II 4.0

Version:

$Id: ParhiMaximumProfitToCostRatioStrategy.java 57040 2010-01-27 20:52:32Z cxh $

Author:

Shahrooz Shahparnia

See Also:

MaximumProfitToCostRatioAnalysis

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Field Summary

private java.util.List	_delayCycle
private java.util.ArrayList	_delayNodeList
private ToIntMapping	_edgeCosts
private ToDoubleMapping	_edgeProfits
private double[][]	_firstOrderLongestPathMatrix
private java.util.ArrayList	_maximumProfitToCostRatioCycle

Constructor Summary

ParhiMaximumProfitToCostRatioStrategy(Graph graph, ToDoubleMapping edgeProfits, ToIntMapping edgeCosts)
Construct an instance of this class.

Method Summary

protected java.lang.Object	_compute() Perform the graph analysis and return the resulting value.
private double	_computeMCM(DirectedGraph graph, ToDoubleMapping edgeLength)
private double[][]	_makeFirstOrderLongestPathMatrix(java.util.HashMap D, DirectedGraph graph, java.util.HashMap predecessorMap)
java.util.List	cycle() Return the nodes on the cycle that corresponds to the maximum profit to cost ratio.
double	maximumRatio() Return the maximum profit to cost ratio of the given graph.
java.lang.String	toString() Return a description of the analyzer.
boolean	valid() Check for compatibility between the analysis and the given graph.

Methods inherited from class ptolemy.graph.analysis.strategy.CachedStrategy

_convertResult, _result, cachingStatus, disableCaching, enableCaching, getCachedResult, graph, obsolete, reset, setCachedResult

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface ptolemy.graph.analysis.analyzer.GraphAnalyzer

graph

Field Detail

_firstOrderLongestPathMatrix

private double[][] _firstOrderLongestPathMatrix

_delayCycle

private java.util.List _delayCycle

_delayNodeList

private java.util.ArrayList _delayNodeList

_maximumProfitToCostRatioCycle

private java.util.ArrayList _maximumProfitToCostRatioCycle

_edgeProfits

private ToDoubleMapping _edgeProfits

_edgeCosts

private ToIntMapping _edgeCosts

Constructor Detail

ParhiMaximumProfitToCostRatioStrategy

public ParhiMaximumProfitToCostRatioStrategy(Graph graph,
                                             ToDoubleMapping edgeProfits,
                                             ToIntMapping edgeCosts)

Construct an instance of this class.

Parameters:

graph - The given graph.

edgeProfits - The profits associated with the edges of the graph.

edgeCosts - The costs associated with the edges of the graph.

Method Detail

cycle

public java.util.List cycle()

Return the nodes on the cycle that corresponds to the maximum profit to cost ratio.

Specified by:

cycle in interface MaximumProfitToCostRatioAnalyzer

Returns:

The nodes on the cycle as an ordered list.

maximumRatio

public double maximumRatio()

Return the maximum profit to cost ratio of the given graph.

Specified by:

maximumRatio in interface MaximumProfitToCostRatioAnalyzer

Returns:

Return the maximum profit to cost ratio of the given graph.

toString

public java.lang.String toString()

Return a description of the analyzer.

Specified by:

toString in interface Analyzer

Overrides:

toString in class CachedStrategy

Returns:

Return a description of the analyzer..

valid

public boolean valid()

Check for compatibility between the analysis and the given graph. A graph needs to be an instance of a DirectedGraph and cyclic in order to have a maximum profit to cost ratio. In addition the given object should be the same graph associated with this analyzer.

Specified by:

valid in interface Analyzer

Returns:

True if the graph is a directed and cyclic graph.

_compute

protected java.lang.Object _compute()

Description copied from class: CachedStrategy

Perform the graph analysis and return the resulting value. Upon entry, CachedStrategy.getCachedResult() provides the result of the previous invocation of the analysis; this value can be used, for example, to facilitate incremental analyses. This method just returns null, and will typically be overridden in each derived class to perform the appropriate graph analysis.

Overrides:

_compute in class CachedStrategy

Returns:

The results of the graph analysis. In this base class, null is returned.

_computeMCM

private double _computeMCM(DirectedGraph graph,
                           ToDoubleMapping edgeLength)

_makeFirstOrderLongestPathMatrix

private double[][] _makeFirstOrderLongestPathMatrix(java.util.HashMap D,
                                                    DirectedGraph graph,
                                                    java.util.HashMap predecessorMap)