- java.lang.Object
-
- org.jgrapht.alg.cycle.HowardMinimumMeanCycle<V,E>
-
- Type Parameters:
V
- graph vertex typeE
- 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 thegraph
.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 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
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 inpolicyGraph
.private boolean
computeVertexDistance(Graph<V,E> component)
This method runs the reverted BFS starting fromcurrentCycleVertex
to update data inpolicyGraph
andvertexDistance
.private void
constructCycle(Graph<V,E> component)
Finds cycle in thepolicyGraph
and computes computes its mean.private void
constructPolicyGraph(Graph<V,E> component)
Computes policy graph forcomponent
and stores result inpolicyGraph
andvertexDistance
.GraphPath<V,E>
getCycle()
Computes cycle with minimum mean.double
getCycleMean()
Computes minimum mean among all cycle.
-
-
-
Field Detail
-
strongConnectivityAlgorithm
private final StrongConnectivityAlgorithm<V,E> strongConnectivityAlgorithm
Algorithm for computing strongly connected components in thegraph
.
-
maximumIterations
private final int maximumIterations
Maximum number of iterations performed during the computation. If not provided via constructor the value if defaulted toInteger.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 givengraph
.- Parameters:
graph
- graph
-
HowardMinimumMeanCycle
public HowardMinimumMeanCycle(Graph<V,E> graph, int maximumIterations)
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 Detail
-
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
public GraphPath<V,E> 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
-
constructPolicyGraph
private void constructPolicyGraph(Graph<V,E> component)
Computes policy graph forcomponent
and stores result inpolicyGraph
andvertexDistance
. 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 thepolicyGraph
and computes computes its mean. The found cycle is identified by a vertexcurrentCycleVertex
. 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 fromcurrentCycleVertex
to update data inpolicyGraph
andvertexDistance
. This step is needed to identify if current value of minimum mean is optimal for thegraph
. This method also usescomparator
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 inpolicyGraph
.- Parameters:
bestCycleVertex
- cycle vertexbestCycleLength
- cycle lengthbestCycleWeight
- cycle weight- Returns:
- constructed minimum mean cycle
-
-