summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
raw | bz2 | zip | gz |
help

author | Peter Kovacs <kpeter@inf.elte.hu> |

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