# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 2009-08-12 09:45:15
# Node ID 0a42883c82217ee3fa7e74b4503eace8048d0af8
# Parent  11c946fa8d13774d947c57e30f3f72cc7b0b3425

Separate group for the min mean cycle classes (#179)

diff --git a/doc/groups.dox b/doc/groups.dox
--- a/doc/groups.dox
+++ b/doc/groups.dox
@@ -391,6 +391,40 @@
 */
 
 /**
+@defgroup min_mean_cycle Minimum Mean Cycle Algorithms
+@ingroup algs
+\brief Algorithms for finding minimum mean cycles.
+
+This group contains the algorithms for finding minimum mean cycles.
+
+The \e minimum \e mean \e cycle \e problem is to find a directed cycle
+of minimum mean length (cost) in a digraph.
+The mean length of a cycle is the average length of its arcs, i.e. the
+ratio between the total length of the cycle and the number of arcs on it.
+
+This problem has an important connection to \e conservative \e length
+\e functions, too. A length function on the arcs of a digraph is called
+conservative if and only if there is no directed cycle of negative total
+length. For an arbitrary length function, the negative of the minimum
+cycle mean is the smallest \f$\epsilon\f$ value so that increasing the
+arc lengths uniformly by \f$\epsilon\f$ results in a conservative length
+function.
+
+LEMON contains three algorithms for solving the minimum mean cycle problem:
+- \ref Karp "Karp"'s original algorithm.
+- \ref HartmannOrlin "Hartmann-Orlin"'s algorithm, which is an improved
+  version of Karp's algorithm.
+- \ref Howard "Howard"'s policy iteration algorithm.
+
+In practice, the Howard algorithm proved to be by far the most efficient
+one, though the best known theoretical bound on its running time is
+exponential.
+Both Karp and HartmannOrlin algorithms run in time O(ne) and use space
+O(n<sup>2</sup>+e), but the latter one is typically faster due to the
+applied early termination scheme.
+*/
+
+/**
 @defgroup graph_properties Connectivity and Other Graph Properties
 @ingroup algs
 \brief Algorithms for discovering the graph properties
diff --git a/lemon/hartmann_orlin.h b/lemon/hartmann_orlin.h
--- a/lemon/hartmann_orlin.h
+++ b/lemon/hartmann_orlin.h
@@ -19,7 +19,7 @@
 #ifndef LEMON_HARTMANN_ORLIN_H
 #define LEMON_HARTMANN_ORLIN_H
 
-/// \ingroup shortest_path
+/// \ingroup min_mean_cycle
 ///
 /// \file
 /// \brief Hartmann-Orlin's algorithm for finding a minimum mean cycle.
@@ -90,7 +90,7 @@
   };
 
 
-  /// \addtogroup shortest_path
+  /// \addtogroup min_mean_cycle
   /// @{
 
   /// \brief Implementation of the Hartmann-Orlin algorithm for finding
@@ -98,8 +98,9 @@
   ///
   /// This class implements the Hartmann-Orlin algorithm for finding
   /// a directed cycle of minimum mean length (cost) in a digraph.
-  /// It is an improved version of \ref Karp "Karp's original algorithm",
+  /// It is an improved version of \ref Karp "Karp"'s original algorithm,
   /// it applies an efficient early termination scheme.
+  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
   ///
   /// \tparam GR The type of the digraph the algorithm runs on.
   /// \tparam LEN The type of the length map. The default
diff --git a/lemon/howard.h b/lemon/howard.h
--- a/lemon/howard.h
+++ b/lemon/howard.h
@@ -19,7 +19,7 @@
 #ifndef LEMON_HOWARD_H
 #define LEMON_HOWARD_H
 
-/// \ingroup shortest_path
+/// \ingroup min_mean_cycle
 ///
 /// \file
 /// \brief Howard's algorithm for finding a minimum mean cycle.
@@ -90,7 +90,7 @@
   };
 
 
-  /// \addtogroup shortest_path
+  /// \addtogroup min_mean_cycle
   /// @{
 
   /// \brief Implementation of Howard's algorithm for finding a minimum
@@ -98,6 +98,9 @@
   ///
   /// This class implements Howard's policy iteration algorithm for finding
   /// a directed cycle of minimum mean length (cost) in a digraph.
+  /// This class provides the most efficient algorithm for the
+  /// minimum mean cycle problem, though the best known theoretical
+  /// bound on its running time is exponential.
   ///
   /// \tparam GR The type of the digraph the algorithm runs on.
   /// \tparam LEN The type of the length map. The default
diff --git a/lemon/karp.h b/lemon/karp.h
--- a/lemon/karp.h
+++ b/lemon/karp.h
@@ -19,7 +19,7 @@
 #ifndef LEMON_KARP_H
 #define LEMON_KARP_H
 
-/// \ingroup shortest_path
+/// \ingroup min_mean_cycle
 ///
 /// \file
 /// \brief Karp's algorithm for finding a minimum mean cycle.
@@ -90,7 +90,7 @@
   };
 
 
-  /// \addtogroup shortest_path
+  /// \addtogroup min_mean_cycle
   /// @{
 
   /// \brief Implementation of Karp's algorithm for finding a minimum
@@ -98,6 +98,7 @@
   ///
   /// This class implements Karp's algorithm for finding a directed
   /// cycle of minimum mean length (cost) in a digraph.
+  /// It runs in time O(ne) and uses space O(n<sup>2</sup>+e).
   ///
   /// \tparam GR The type of the digraph the algorithm runs on.
   /// \tparam LEN The type of the length map. The default