public class KarpCycleMeanStrategy extends CachedStrategy implements CycleMeanAnalyzer
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.
CycleMeanAnalysis
Constructor and Description |
---|
KarpCycleMeanStrategy(Graph graph,
ToDoubleMapping edgeLengths)
Construct a maximum cycle mean analyzer for a given graph, using the
Karp's algorithm.
|
Modifier and Type | Method and Description |
---|---|
protected java.lang.Object |
_compute()
Perform the graph analysis and return the resulting value.
|
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.
|
_convertResult, _result, cachingStatus, disableCaching, enableCaching, getCachedResult, graph, obsolete, reset, setCachedResult
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
graph
public KarpCycleMeanStrategy(Graph graph, ToDoubleMapping edgeLengths)
graph
- The given graph.edgeLengths
- The lengths associated with the edges of the given
graph.public java.util.List cycle()
cycle
in interface CycleMeanAnalyzer
public double cycleMean(boolean maximum)
maximum
- True if the maximum cycle mean is requested.public double maximumCycleMean()
maximumCycleMean
in interface CycleMeanAnalyzer
public double minimumCycleMean()
minimumCycleMean
in interface CycleMeanAnalyzer
public java.lang.String toString()
toString
in interface Analyzer
toString
in class CachedStrategy
public boolean valid()
protected java.lang.Object _compute()
CachedStrategy
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._compute
in class CachedStrategy