1.1 --- a/doc/groups.dox	Tue Aug 11 22:52:35 2009 +0200
     1.2 +++ b/doc/groups.dox	Wed Aug 12 09:45:15 2009 +0200
     1.3 @@ -391,6 +391,40 @@
     1.4  */
     1.5  
     1.6  /**
     1.7 +@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
     1.8 +@ingroup algs
     1.9 +\brief Algorithms for finding minimum mean cycles.
    1.10 +
    1.11 +This group contains the algorithms for finding minimum mean cycles.
    1.12 +
    1.13 +The \e minimum \e mean \e cycle \e problem is to find a directed cycle
    1.14 +of minimum mean length (cost) in a digraph.
    1.15 +The mean length of a cycle is the average length of its arcs, i.e. the
    1.16 +ratio between the total length of the cycle and the number of arcs on it.
    1.17 +
    1.18 +This problem has an important connection to \e conservative \e length
    1.19 +\e functions, too. A length function on the arcs of a digraph is called
    1.20 +conservative if and only if there is no directed cycle of negative total
    1.21 +length. For an arbitrary length function, the negative of the minimum
    1.22 +cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
    1.23 +arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
    1.24 +function.
    1.25 +
    1.26 +LEMON contains three algorithms for solving the minimum mean cycle problem:
    1.27 +- \ref Karp "Karp"'s original algorithm.
    1.28 +- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
    1.29 +  version of Karp's algorithm.
    1.30 +- \ref Howard "Howard"'s policy iteration algorithm.
    1.31 +
    1.32 +In practice, the Howard algorithm proved to be by far the most efficient
    1.33 +one, though the best known theoretical bound on its running time is
    1.34 +exponential.
    1.35 +Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
    1.36 +O(n<sup>2</sup>+e), but the latter one is typically faster due to the
    1.37 +applied early termination scheme.
    1.38 +*/
    1.39 +
    1.40 +/**
    1.41  @defgroup graph_properties Connectivity and Other Graph Properties
    1.42  @ingroup algs
    1.43  \brief Algorithms for discovering the graph properties

     2.1 --- a/lemon/hartmann_orlin.h	Tue Aug 11 22:52:35 2009 +0200
     2.2 +++ b/lemon/hartmann_orlin.h	Wed Aug 12 09:45:15 2009 +0200
     2.3 @@ -19,7 +19,7 @@
     2.4  #ifndef LEMON_HARTMANN_ORLIN_H
     2.5  #define LEMON_HARTMANN_ORLIN_H
     2.6  
     2.7 -/// \ingroup shortest_path
     2.8 +/// \ingroup min_mean_cycle
     2.9  ///
    2.10  /// \file
    2.11  /// \brief Hartmann-Orlin's algorithm for finding a minimum mean cycle.
    2.12 @@ -90,7 +90,7 @@
    2.13    };
    2.14  
    2.15  
    2.16 -  /// \addtogroup shortest_path
    2.17 +  /// \addtogroup min_mean_cycle
    2.18    /// @{
    2.19  
    2.20    /// \brief Implementation of the Hartmann-Orlin algorithm for finding
    2.21 @@ -98,8 +98,9 @@
    2.22    ///
    2.23    /// This class implements the Hartmann-Orlin algorithm for finding
    2.24    /// a directed cycle of minimum mean length (cost) in a digraph.
    2.25 -  /// It is an improved version of \ref Karp "Karp's original algorithm",
    2.26 +  /// It is an improved version of \ref Karp "Karp"'s original algorithm,
    2.27    /// it applies an efficient early termination scheme.
    2.28 +  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    2.29    ///
    2.30    /// \tparam GR The type of the digraph the algorithm runs on.
    2.31    /// \tparam LEN The type of the length map. The default

     3.1 --- a/lemon/howard.h	Tue Aug 11 22:52:35 2009 +0200
     3.2 +++ b/lemon/howard.h	Wed Aug 12 09:45:15 2009 +0200
     3.3 @@ -19,7 +19,7 @@
     3.4  #ifndef LEMON_HOWARD_H
     3.5  #define LEMON_HOWARD_H
     3.6  
     3.7 -/// \ingroup shortest_path
     3.8 +/// \ingroup min_mean_cycle
     3.9  ///
    3.10  /// \file
    3.11  /// \brief Howard's algorithm for finding a minimum mean cycle.
    3.12 @@ -90,7 +90,7 @@
    3.13    };
    3.14  
    3.15  
    3.16 -  /// \addtogroup shortest_path
    3.17 +  /// \addtogroup min_mean_cycle
    3.18    /// @{
    3.19  
    3.20    /// \brief Implementation of Howard's algorithm for finding a minimum
    3.21 @@ -98,6 +98,9 @@
    3.22    ///
    3.23    /// This class implements Howard's policy iteration algorithm for finding
    3.24    /// a directed cycle of minimum mean length (cost) in a digraph.
    3.25 +  /// This class provides the most efficient algorithm for the
    3.26 +  /// minimum mean cycle problem, though the best known theoretical
    3.27 +  /// bound on its running time is exponential.
    3.28    ///
    3.29    /// \tparam GR The type of the digraph the algorithm runs on.
    3.30    /// \tparam LEN The type of the length map. The default

     4.1 --- a/lemon/karp.h	Tue Aug 11 22:52:35 2009 +0200
     4.2 +++ b/lemon/karp.h	Wed Aug 12 09:45:15 2009 +0200
     4.3 @@ -19,7 +19,7 @@
     4.4  #ifndef LEMON_KARP_H
     4.5  #define LEMON_KARP_H
     4.6  
     4.7 -/// \ingroup shortest_path
     4.8 +/// \ingroup min_mean_cycle
     4.9  ///
    4.10  /// \file
    4.11  /// \brief Karp's algorithm for finding a minimum mean cycle.
    4.12 @@ -90,7 +90,7 @@
    4.13    };
    4.14  
    4.15  
    4.16 -  /// \addtogroup shortest_path
    4.17 +  /// \addtogroup min_mean_cycle
    4.18    /// @{
    4.19  
    4.20    /// \brief Implementation of Karp's algorithm for finding a minimum
    4.21 @@ -98,6 +98,7 @@
    4.22    ///
    4.23    /// This class implements Karp's algorithm for finding a directed
    4.24    /// cycle of minimum mean length (cost) in a digraph.
    4.25 +  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
    4.26    ///
    4.27    /// \tparam GR The type of the digraph the algorithm runs on.
    4.28    /// \tparam LEN The type of the length map. The default