LEMON/LEMON-main Changeset - r768:0a42883c8221

Repositories » LEMON » LEMON-main

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r768:0a42883c8221

« 767:11c946

769:e746fb »

r768:0a42883c8221

Wed, 12 Aug 2009 09:45:15

[Not Reviewed]

0 comments (0 inline)

kpeter (Peter Kovacs)
kpeter@inf.elte.hu

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

0 4 0

default

4 files changed with 46 insertions and 7 deletions:

doc/groups.dox

lemon/hartmann_orlin.h

lemon/howard.h

lemon/karp.h

↑ Collapse diff ↑

doc/groups.dox

Show inline comments

@@ -382,24 +382,58 @@
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
 		  calculating minimum cut in undirected graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
 		see the \ref max_flow "maximum flow problem".
 		*/
 		/**
 		@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
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		*/
 		/**

lemon/hartmann_orlin.h

Show inline comments

@@ -10,25 +10,25 @@
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#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.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
@@ -81,34 +81,35 @@
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
-		  /// \addtogroup shortest_path
+		  /// \addtogroup min_mean_cycle
 		  /// @{
 		  /// \brief Implementation of the Hartmann-Orlin algorithm for finding
 		  /// a minimum mean cycle.
 		  ///
 		  /// 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
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = HartmannOrlinDefaultTraits<GR, LEN> >
 		#endif
 		  class HartmannOrlin

lemon/howard.h

Show inline comments

@@ -10,25 +10,25 @@
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#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.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
@@ -81,32 +81,35 @@
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
-		  /// \addtogroup shortest_path
+		  /// \addtogroup min_mean_cycle
 		  /// @{
 		  /// \brief Implementation of Howard's algorithm for finding a minimum
 		  /// mean cycle.
 		  ///
 		  /// 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
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = HowardDefaultTraits<GR, LEN> >
 		#endif
 		  class Howard

lemon/karp.h

Show inline comments

@@ -10,25 +10,25 @@
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#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.
 		#include <vector>
 		#include <limits>
 		#include <lemon/core.h>
 		#include <lemon/path.h>
 		#include <lemon/tolerance.h>
 		#include <lemon/connectivity.h>
 		namespace lemon {
@@ -81,32 +81,33 @@
 		    typedef LEN LengthMap;
 		    typedef typename LengthMap::Value Value;
 		#ifdef LEMON_HAVE_LONG_LONG
 		    typedef long long LargeValue;
 		#else
 		    typedef long LargeValue;
 		#endif
 		    typedef lemon::Tolerance<LargeValue> Tolerance;
 		    typedef lemon::Path<Digraph> Path;
 		  };
-		  /// \addtogroup shortest_path
+		  /// \addtogroup min_mean_cycle
 		  /// @{
 		  /// \brief Implementation of Karp's algorithm for finding a minimum
 		  /// mean cycle.
 		  ///
 		  /// 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
 		  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		#ifdef DOXYGEN
 		  template <typename GR, typename LEN, typename TR>
 		#else
 		  template < typename GR,
 		             typename LEN = typename GR::template ArcMap<int>,
 		             typename TR = KarpDefaultTraits<GR, LEN> >
 		#endif
 		  class Karp

0 comments (0 inline)

RhodeCode

Login to your account