Changeset 764:1fac515a59c1 in lemon-main

Timestamp:

08/10/09 14:50:57 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Rename MinMeanCycle? to Howard (#179)

Files:

• lemon/Makefile.am (modified) (2 diffs)
• lemon/howard.h (moved) (moved from lemon/min_mean_cycle.h) (15 diffs)
• test/min_mean_cycle_test.cc (modified) (3 diffs)

lemon/Makefile.am

@@ -84 +84 @@
         lemon/graph_to_eps.h \
         lemon/grid_graph.h \
+        lemon/howard.h \
         lemon/hypercube_graph.h \
         lemon/kruskal.h \
@@ -98 +99 @@
         lemon/math.h \
         lemon/min_cost_arborescence.h \
-        lemon/min_mean_cycle.h \
         lemon/nauty_reader.h \
         lemon/network_simplex.h \

lemon/howard.h

@@ -17 +17 @@
  */
 
-#ifndef LEMON_MIN_MEAN_CYCLE_H
-#define LEMON_MIN_MEAN_CYCLE_H
+#ifndef LEMON_HOWARD_H
+#define LEMON_HOWARD_H
 
 /// \ingroup shortest_path
@@ -34 +34 @@
 namespace lemon {
 
-  /// \brief Default traits class of MinMeanCycle class.
+  /// \brief Default traits class of Howard class.
   ///
-  /// Default traits class of MinMeanCycle class.
+  /// Default traits class of Howard class.
   /// \tparam GR The type of the digraph.
   /// \tparam LEN The type of the length map.
@@ -46 +46 @@
     bool integer = std::numeric_limits<typename LEN::Value>::is_integer>
 #endif
-  struct MinMeanCycleDefaultTraits
+  struct HowardDefaultTraits
   {
     /// The type of the digraph
@@ -76 +76 @@
   // Default traits class for integer value types
   template <typename GR, typename LEN>
-  struct MinMeanCycleDefaultTraits<GR, LEN, true>
+  struct HowardDefaultTraits<GR, LEN, true>
   {
     typedef GR Digraph;
@@ -97 +97 @@
   /// mean cycle.
   ///
-  /// \ref MinMeanCycle implements Howard's algorithm for finding a
-  /// directed cycle of minimum mean length (cost) in a digraph.
+  /// This class implements Howard's policy iteration algorithm for finding
+  /// a directed cycle of minimum mean length (cost) in a digraph.
   ///
   /// \tparam GR The type of the digraph the algorithm runs on.
@@ -108 +108 @@
   template < typename GR,
              typename LEN = typename GR::template ArcMap<int>,
-             typename TR = MinMeanCycleDefaultTraits<GR, LEN> >
+             typename TR = HowardDefaultTraits<GR, LEN> >
 #endif
-  class MinMeanCycle
+  class Howard
   {
   public:
@@ -124 +124 @@
     ///
     /// The large value type used for internal computations.
-    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
+    /// Using the \ref HowardDefaultTraits "default traits class",
     /// it is \c long \c long if the \c Value type is integer,
     /// otherwise it is \c double.
@@ -135 +135 @@
     ///
     /// The path type of the found cycles.
-    /// Using the \ref MinMeanCycleDefaultTraits "default traits class",
+    /// Using the \ref HowardDefaultTraits "default traits class",
     /// it is \ref lemon::Path "Path<Digraph>".
     typedef typename TR::Path Path;
 
-    /// The \ref MinMeanCycleDefaultTraits "traits class" of the algorithm
+    /// The \ref HowardDefaultTraits "traits class" of the algorithm
     typedef TR Traits;
 
@@ -197 +197 @@
     template <typename T>
     struct SetLargeValue
-      : public MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > {
-      typedef MinMeanCycle<GR, LEN, SetLargeValueTraits<T> > Create;
+      : public Howard<GR, LEN, SetLargeValueTraits<T> > {
+      typedef Howard<GR, LEN, SetLargeValueTraits<T> > Create;
     };
 
@@ -215 +215 @@
     template <typename T>
     struct SetPath
-      : public MinMeanCycle<GR, LEN, SetPathTraits<T> > {
-      typedef MinMeanCycle<GR, LEN, SetPathTraits<T> > Create;
+      : public Howard<GR, LEN, SetPathTraits<T> > {
+      typedef Howard<GR, LEN, SetPathTraits<T> > Create;
     };
     
@@ -229 +229 @@
     /// \param digraph The digraph the algorithm runs on.
     /// \param length The lengths (costs) of the arcs.
-    MinMeanCycle( const Digraph &digraph,
-                  const LengthMap &length ) :
+    Howard( const Digraph &digraph,
+            const LengthMap &length ) :
       _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false),
       _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph),
@@ -237 +237 @@
 
     /// Destructor.
-    ~MinMeanCycle() {
+    ~Howard() {
       if (_local_path) delete _cycle_path;
     }
@@ -255 +255 @@
     ///
     /// \return <tt>(*this)</tt>
-    MinMeanCycle& cycle(Path &path) {
+    Howard& cycle(Path &path) {
       if (_local_path) {
         delete _cycle_path;
@@ -560 +560 @@
     }
 
-  }; //class MinMeanCycle
+  }; //class Howard
 
   ///@}
@@ -566 +566 @@
 } //namespace lemon
 
-#endif //LEMON_MIN_MEAN_CYCLE_H
+#endif //LEMON_HOWARD_H

test/min_mean_cycle_test.cc

@@ -22 +22 @@
 #include <lemon/smart_graph.h>
 #include <lemon/lgf_reader.h>
-#include <lemon/min_mean_cycle.h>
+#include <lemon/howard.h>
 #include <lemon/path.h>
 #include <lemon/concepts/digraph.h>
@@ -142 +142 @@
   {
     typedef concepts::Digraph GR;
-    typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
-    typedef MinMeanCycle<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
+    typedef Howard<GR, concepts::ReadMap<GR::Arc, int> > IntMmcAlg;
+    typedef Howard<GR, concepts::ReadMap<GR::Arc, float> > FloatMmcAlg;
     
     checkConcept<MmcClassConcept<GR, int>, IntMmcAlg>();
@@ -175 +175 @@
       run();
 
-    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l1, c1,  6, 3);
-    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l2, c2,  5, 2);
-    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l3, c3,  0, 1);
-    checkMmcAlg<MinMeanCycle<GR, IntArcMap> >(gr, l4, c4, -1, 1);
+    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l1, c1,  6, 3);
+    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l2, c2,  5, 2);
+    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l3, c3,  0, 1);
+    checkMmcAlg<Howard<GR, IntArcMap> >(gr, l4, c4, -1, 1);
   }