ptolemy.graph.analysis.strategy
Class KarpCycleMeanStrategy

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

All Implemented Interfaces:

Analyzer, CycleMeanAnalyzer, GraphAnalyzer

public class KarpCycleMeanStrategy
extends CachedStrategy
implements CycleMeanAnalyzer

An analyzer for computing the maximum/minimum cycle mean of a graph. This implementation uses the Karp's algorithm described in:

A.Dasdan, R.K. Gupta, "Faster Maximum and Minimum Mean Cycle Algorithms for System Performance".

Note that the mathematical definition of maximum cycle mean and maximum profit to cost are different, though some time the name "maximum cycle mean" is used to refer to the maximum profit to cost ratio.

Since:

Ptolemy II 4.0

Version:

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

Author:

Shahrooz Shahparnia

See Also:

CycleMeanAnalysis

Accepted Rating:

Red (ssb)

Proposed Rating:

Red (shahrooz)

Field Summary

private java.util.ArrayList	_cycle
private ToDoubleMapping	_edgeLengths
private boolean	_maximumAnalysis
private java.util.ArrayList	_nodesOnCycle

Constructor Summary

KarpCycleMeanStrategy(Graph graph, ToDoubleMapping edgeLengths)
Construct a maximum cycle mean analyzer for a given graph, using the Karp's algorithm.

Method Summary

protected java.lang.Object	_compute() Perform the graph analysis and return the resulting value.
private double	_computeMCMOfSCC(DirectedGraph directedCyclicGraph)
private double	_getCost(Node u, Node v)
java.util.List	cycle() Return the nodes on the cycle that corresponds to the maximum/minimum cycle mean as an ordered list.
double	cycleMean(boolean maximum) Finds the cycle mean for a given directed graph.
double	maximumCycleMean() Return the maximum cycle mean.
double	minimumCycleMean() Return minimum cycle mean.
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

_maximumAnalysis

private boolean _maximumAnalysis

_nodesOnCycle

private java.util.ArrayList _nodesOnCycle

_cycle

private java.util.ArrayList _cycle

_edgeLengths

private ToDoubleMapping _edgeLengths

Constructor Detail

KarpCycleMeanStrategy

public KarpCycleMeanStrategy(Graph graph,
                             ToDoubleMapping edgeLengths)

Construct a maximum cycle mean analyzer for a given graph, using the Karp's algorithm.

Parameters:

graph - The given graph.

edgeLengths - The lengths associated with the edges of the given graph.

Method Detail

cycle

public java.util.List cycle()

Return the nodes on the cycle that corresponds to the maximum/minimum cycle mean as an ordered list. If there is more than one cycle with the same maximal/minimal MCM, one of them is returned randomly, but the same cycle is returned by different invocations of the method, unless the graph changes. A call to maximumCycleMean() or minimumCycleMean() should precede a call to this method, in order to return a valid cycle.

Specified by:

cycle in interface CycleMeanAnalyzer

Returns:

The nodes on the cycle that corresponds to one of the maximum/minimum cycle means as an ordered list.

cycleMean

public double cycleMean(boolean maximum)

Finds the cycle mean for a given directed graph. Strongly connected components are being considered separately. And the CycleMean is the maximum/minimum among them. When there are multiple edges between two nodes, the edge with the maximum/minimum weight is considered for the cycle that gives the maximum/minimum cycle mean.

Parameters:

maximum - True if the maximum cycle mean is requested.

Returns:

The maximum/minimum cycle mean.

maximumCycleMean

public double maximumCycleMean()

Return the maximum cycle mean.

Specified by:

maximumCycleMean in interface CycleMeanAnalyzer

Returns:

The maximum cycle mean value.

minimumCycleMean

public double minimumCycleMean()

Return minimum cycle mean.

Specified by:

minimumCycleMean in interface CycleMeanAnalyzer

Returns:

The minimum cycle mean value.

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 cycle mean. 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.

_computeMCMOfSCC

private double _computeMCMOfSCC(DirectedGraph directedCyclicGraph)

_getCost

private double _getCost(Node u,
                        Node v)