 Type Parameters:
V
 graph vertex typeE
 graph edge type
 All Implemented Interfaces:
MinimumCycleMeanAlgorithm<V,
E>
The algorithm is described in the article: Ali Dasdan, Sandy S. Irani, and Rajesh K. Gupta. 1999. Efficient algorithms for optimum cycle mean and optimum cost to time ratio problems. In Proceedings of the 36th annual ACM/IEEE Design Automation Conference (DAC ’99). Association for Computing Machinery, New York, NY, USA, 37–42. DOI:https://doi.org/10.1145/309847.309862
Firstly, the graph is divided into strongly connected components. The minimum cycle mean is then computed as the globally minimum cycle mean over all components. In the process the necessary information is recorded to be able to reconstruct the cycle with minimum mean.
The computations are divided into iterations. In each iteration the algorithm tries to update current minimum cycle mean value. There is a possibility to limit the total number of iteration via a constructor parameter.
 Author:
 Semen Chudakov

Constructor Summary
ConstructorDescriptionHowardMinimumMeanCycle
(Graph<V, E> graph) Constructs an instance of the algorithm for the givengraph
.HowardMinimumMeanCycle
(Graph<V, E> graph, int maximumIterations) Constructs an instance of the algorithm for the givengraph
andmaximumIterations
.HowardMinimumMeanCycle
(Graph<V, E> graph, int maximumIterations, StrongConnectivityAlgorithm<V, E> strongConnectivityAlgorithm, double toleranceEpsilon) Constructs an instance of the algorithm for the givengraph
,maximumIterations
,strongConnectivityAlgorithm
andtoleranceEpsilon
. 
Method Summary
Modifier and TypeMethodDescriptiongetCycle()
Computes cycle with minimum mean.double
Computes minimum mean among all cycle.

Constructor Details

HowardMinimumMeanCycle
Constructs an instance of the algorithm for the givengraph
. Parameters:
graph
 graph

HowardMinimumMeanCycle
Constructs an instance of the algorithm for the givengraph
andmaximumIterations
. Parameters:
graph
 graphmaximumIterations
 maximum number of iterations

HowardMinimumMeanCycle
public HowardMinimumMeanCycle(Graph<V, E> graph, int maximumIterations, StrongConnectivityAlgorithm<V, E> strongConnectivityAlgorithm, double toleranceEpsilon) Constructs an instance of the algorithm for the givengraph
,maximumIterations
,strongConnectivityAlgorithm
andtoleranceEpsilon
. Parameters:
graph
 graphmaximumIterations
 maximum number of iterationsstrongConnectivityAlgorithm
 algorithm to compute strongly connected componentstoleranceEpsilon
 tolerance to compare floating point numbers


Method Details

getCycleMean
public double getCycleMean()Computes minimum mean among all cycle. ReturnsDouble.POSITIVE_INFINITY
if no cycle has been found. Specified by:
getCycleMean
in interfaceMinimumCycleMeanAlgorithm<V,
E>  Returns:
 minimum mean

getCycle
Computes cycle with minimum mean. Returns $null$ if no cycle has been found. Specified by:
getCycle
in interfaceMinimumCycleMeanAlgorithm<V,
E>  Returns:
 cycle with minimum mean
