Module org.jgrapht.core
Package org.jgrapht.alg.cycle

Class 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.

    Author:
    Semen Chudakov

    • 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
      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

    • 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