public class CycleMeanAnalysis extends Analysis
The analyzer associated to this analysis, adds up the cost of the edges on different cycles and divides it by the number of edges in that cycle, then picks the maximum/minimum of them.
Strongly connected components are being processed separately, and the cycle mean has the maximum/minimum value 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.
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.
For a detailed mathematical description of the problem, refer to:
Ali Dasdan , Sandy S. Irani , Rajesh K. Gupta, Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems, Proceedings of the 36th ACM/IEEE conference on Design automation conference, p.37-42, June 21-25, 1999, New Orleans, Louisiana, United States
MaximumProfitToCostRatioAnalysis
Constructor and Description |
---|
CycleMeanAnalysis(CycleMeanAnalyzer analyzer)
Construct a maximum cycle mean analysis associated with a graph with a
given analyzer.
|
CycleMeanAnalysis(Graph graph,
ToDoubleMapping edgeLengths)
Construct a maximum cycle mean analysis associated with a graph with a
default analyzer.
|
Modifier and Type | Method and Description |
---|---|
java.util.List |
cycle()
Return the nodes on the cycle that corresponds to the maximum/minimum
cycle mean as an ordered list.
|
double |
maximumCycleMean()
Return the maximum cycle mean value.
|
double |
minimumCycleMean()
Return minimum cycle mean value.
|
java.lang.String |
toString()
Return a description of the analysis and the associated analyzer.
|
boolean |
validAnalyzerInterface(Analyzer analyzer)
Check if a given analyzer is compatible with this analysis.
|
analyzer, changeAnalyzer, graph, valid
public CycleMeanAnalysis(Graph graph, ToDoubleMapping edgeLengths)
graph
- The given graph.edgeLengths
- The lengths associated with the edges of the graph.public CycleMeanAnalysis(CycleMeanAnalyzer analyzer)
analyzer
- The given analyzer.public java.util.List cycle()
public double maximumCycleMean()
public double minimumCycleMean()
public java.lang.String toString()
public boolean validAnalyzerInterface(Analyzer analyzer)
validAnalyzerInterface
in class Analysis
analyzer
- The given analyzer.