java.lang.Object
- org.jgrapht.alg.cycle.HowardMinimumMeanCycle<V,E>

Type Parameters:

V - graph vertex type

E - graph edge type

All Implemented Interfaces:

MinimumCycleMeanAlgorithm<V,E>
```
public class HowardMinimumMeanCycle<V,E>
extends java.lang.Object
implements MinimumCycleMeanAlgorithm<V,E>
```
Implementation of Howard`s algorithm for finding minimum cycle mean in a graph.
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.

Field Summary

Fields
Modifier and Type	Field	Description
`private java.util.Comparator<java.lang.Double>`	`comparator`	Used to compare floating point numbers.
`private int`	`currentCycleLength`	Length of a cycle found on current iteration.
`private V`	`currentCycleVertex`	Vertex which is used to reconstruct the cycle found on current iteration.
`private double`	`currentCycleWeight`	Total weight of a cycle found on current iteration.
`private Graph<V,E>`	`graph`	The underlying graph.
`private boolean`	`isCurrentCycleFound`	Determines if a cycle is found on current iteration.
`private int`	`maximumIterations`	Maximum number of iterations performed during the computation.
`private java.util.Map<V,E>`	`policyGraph`	For each vertex contains an edge, which together for the policy graph on current iteration.
`private java.util.Map<V,java.lang.Boolean>`	`reachedVertices`	For each vertex indicates, if it has been reached by a search during computing vertices distance in the policy graph.
`private StrongConnectivityAlgorithm<V,E>`	`strongConnectivityAlgorithm`	Algorithm for computing strongly connected components in the `graph`.
`private java.util.Map<V,java.lang.Double>`	`vertexDistance`	For each vertex stores its distance in the policy graph.
`private java.util.Map<V,java.lang.Integer>`	`vertexLevel`	For each vertex stores its level which is used to find a cycle in the policy graph.

Constructor Summary

Constructors
Constructor	Description
`HowardMinimumMeanCycle(Graph<V,E> graph)`	Constructs an instance of the algorithm for the given `graph`.
`HowardMinimumMeanCycle(Graph<V,E> graph, int maximumIterations)`	Constructs an instance of the algorithm for the given `graph` and `maximumIterations`.
`HowardMinimumMeanCycle(Graph<V,E> graph, int maximumIterations, StrongConnectivityAlgorithm<V,E> strongConnectivityAlgorithm, double toleranceEpsilon)`	Constructs an instance of the algorithm for the given `graph`, `maximumIterations`, `strongConnectivityAlgorithm` and `toleranceEpsilon`.

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method	Description
`private GraphPath<V,E>`	`buildPath(V bestCycleVertex, int bestCycleLength, double bestCycleWeight)`	Constructs cycle with minimum mean using information in `policyGraph`.
`private boolean`	`computeVertexDistance(Graph<V,E> component)`	This method runs the reverted BFS starting from `currentCycleVertex` to update data in `policyGraph` and `vertexDistance`.
`private void`	`constructCycle(Graph<V,E> component)`	Finds cycle in the `policyGraph` and computes computes its mean.
`private void`	`constructPolicyGraph(Graph<V,E> component)`	Computes policy graph for `component` and stores result in `policyGraph` and `vertexDistance`.
`GraphPath<V,E>`	`getCycle()`	Computes cycle with minimum mean.
`double`	`getCycleMean()`	Computes minimum mean among all cycle.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - graph
```
private final Graph<V,E> graph
```
    The underlying graph.
  - strongConnectivityAlgorithm
```
private final StrongConnectivityAlgorithm<V,E> strongConnectivityAlgorithm
```
    Algorithm for computing strongly connected components in the graph.
  - maximumIterations
```
private final int maximumIterations
```
    Maximum number of iterations performed during the computation. If not provided via constructor the value if defaulted to Integer.MAX_VALUE.
  - comparator
```
private final java.util.Comparator<java.lang.Double> comparator
```
    Used to compare floating point numbers.
  - isCurrentCycleFound
```
private boolean isCurrentCycleFound
```
    Determines if a cycle is found on current iteration.
  - currentCycleWeight
```
private double currentCycleWeight
```
    Total weight of a cycle found on current iteration.
  - currentCycleLength
```
private int currentCycleLength
```
    Length of a cycle found on current iteration.
  - currentCycleVertex
```
private V currentCycleVertex
```
    Vertex which is used to reconstruct the cycle found on current iteration.
  - policyGraph
```
private java.util.Map<V,E> policyGraph
```
    For each vertex contains an edge, which together for the policy graph on current iteration.
  - reachedVertices
```
private java.util.Map<V,java.lang.Boolean> reachedVertices
```
    For each vertex indicates, if it has been reached by a search during computing vertices distance in the policy graph.
  - vertexLevel
```
private java.util.Map<V,java.lang.Integer> vertexLevel
```
    For each vertex stores its level which is used to find a cycle in the policy graph.
  - vertexDistance
```
private java.util.Map<V,java.lang.Double> vertexDistance
```
    For each vertex stores its distance in the policy graph.
- Constructor Detail
  - HowardMinimumMeanCycle
```
public HowardMinimumMeanCycle(Graph<V,E> graph)
```
    Constructs an instance of the algorithm for the given graph.
    
    Parameters:
    
    graph - graph
  - HowardMinimumMeanCycle
```
public HowardMinimumMeanCycle(Graph<V,E> graph,
                              int maximumIterations)
```
    Constructs an instance of the algorithm for the given graph and maximumIterations.
    
    Parameters:
    
    graph - graph
    
    maximumIterations - 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 given graph, maximumIterations, strongConnectivityAlgorithm and toleranceEpsilon.
    
    Parameters:
    
    graph - graph
    
    maximumIterations - maximum number of iterations
    
    strongConnectivityAlgorithm - algorithm to compute strongly connected components
    
    toleranceEpsilon - tolerance to compare floating point numbers
- Method Detail
  - getCycleMean
```
public double getCycleMean()
```
    Computes minimum mean among all cycle. Returns Double.POSITIVE_INFINITY if no cycle has been found.
    
    Specified by:
    
    getCycleMean in interface MinimumCycleMeanAlgorithm<V,E>
    
    Returns:
    
    minimum mean
  - getCycle
```
public GraphPath<V,E> getCycle()
```
    Computes cycle with minimum mean. Returns $null$ if no cycle has been found.
    
    Specified by:
    
    getCycle in interface MinimumCycleMeanAlgorithm<V,E>
    
    Returns:
    
    cycle with minimum mean
  - constructPolicyGraph
```
private void constructPolicyGraph(Graph<V,E> component)
```
    Computes policy graph for component and stores result in policyGraph and vertexDistance. For every vertex in the policy graph an edge with the minimum weight is retained in the policy graph.
    
    Parameters:
    
    component - connected component
  - constructCycle
```
private void constructCycle(Graph<V,E> component)
```
    Finds cycle in the policyGraph and computes computes its mean. The found cycle is identified by a vertex currentCycleVertex. The cycle returned by this method does not necessarily has the smalles mean over all cycles in the policy graph.
    To find cycles this methods assigns a level to each vertex. Initially every vertex has a level equal to $-1$ which means that the vertex has not been visited. During the computations this method starts DFS from every not visited vertex and assigns a unique positive level $l$ to every traversed vertex. If DFS comes across a vertex with level $l$ this indicates that a cycle has been detected.
    
    Parameters:
    
    component - connected component
  - computeVertexDistance
```
private boolean computeVertexDistance(Graph<V,E> component)
```
    This method runs the reverted BFS starting from currentCycleVertex to update data in policyGraph and vertexDistance. This step is needed to identify if current value of minimum mean is optimal for the graph. This method also uses comparator to find out if update value of minium mean is sufficiently smaller than the previous one.
    
    Parameters:
    
    component - connected component
    
    Returns:
    
    if the currently best mean has been improved
  - buildPath
```
private GraphPath<V,E> buildPath(V bestCycleVertex,
                                       int bestCycleLength,
                                       double bestCycleWeight)
```
    Constructs cycle with minimum mean using information in policyGraph.
    
    Parameters:
    
    bestCycleVertex - cycle vertex
    
    bestCycleLength - cycle length
    
    bestCycleWeight - cycle weight
    
    Returns:
    
    constructed minimum mean cycle

Class HowardMinimumMeanCycle<V,​E>

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

graph

strongConnectivityAlgorithm

maximumIterations

comparator

isCurrentCycleFound

currentCycleWeight

currentCycleLength

currentCycleVertex

policyGraph

reachedVertices

vertexLevel

vertexDistance

Constructor Detail

HowardMinimumMeanCycle

HowardMinimumMeanCycle

HowardMinimumMeanCycle

Method Detail

getCycleMean

getCycle

constructPolicyGraph

constructCycle

computeVertexDistance

buildPath

Class HowardMinimumMeanCycle<V,E>