author Peter Kovacs Wed, 12 Aug 2009 09:45:15 +0200 changeset 815 0a42883c8221 parent 814 11c946fa8d13 child 816 e746fb14e680
Separate group for the min mean cycle classes (#179)
 doc/groups.dox file | annotate | diff | comparison | revisions lemon/hartmann_orlin.h file | annotate | diff | comparison | revisions lemon/howard.h file | annotate | diff | comparison | revisions lemon/karp.h file | annotate | diff | comparison | revisions
     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.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.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