Changes in / [1014:bc726f4892c7:1011:9a6c9d4ee77b] in lemon-main

Files:

• lemon/cycle_canceling.h (modified) (4 diffs)
• lemon/howard_mmc.h (modified) (4 diffs)
• test/min_mean_cycle_test.cc (modified) (2 diffs)

lemon/cycle_canceling.h

@@ -36 +36 @@
 #include <lemon/bellman_ford.h>
 #include <lemon/howard_mmc.h>
-#include <lemon/hartmann_orlin_mmc.h>
 
 namespace lemon {
@@ -929 +928 @@
     // Execute the "Minimum Mean Cycle Canceling" method
     void startMinMeanCycleCanceling() {
-      typedef Path<StaticDigraph> SPath;
+      typedef SimplePath<StaticDigraph> SPath;
       typedef typename SPath::ArcIt SPathArcIt;
       typedef typename HowardMmc<StaticDigraph, CostArcMap>
-        ::template SetPath<SPath>::Create HwMmc;
-      typedef typename HartmannOrlinMmc<StaticDigraph, CostArcMap>
-        ::template SetPath<SPath>::Create HoMmc;
-
-      const double HW_ITER_LIMIT_FACTOR = 1.0;
-      const int HW_ITER_LIMIT_MIN_VALUE = 5;
-
-      const int hw_iter_limit =
-          std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num),
-                   HW_ITER_LIMIT_MIN_VALUE);
+        ::template SetPath<SPath>::Create MMC;
 
       SPath cycle;
-      HwMmc hw_mmc(_sgr, _cost_map);
-      hw_mmc.cycle(cycle);
+      MMC mmc(_sgr, _cost_map);
+      mmc.cycle(cycle);
       buildResidualNetwork();
-      while (true) {
-        
-        typename HwMmc::TerminationCause hw_tc =
-            hw_mmc.findCycleMean(hw_iter_limit);
-        if (hw_tc == HwMmc::ITERATION_LIMIT) {
-          // Howard's algorithm reached the iteration limit, start a
-          // strongly polynomial algorithm instead
-          HoMmc ho_mmc(_sgr, _cost_map);
-          ho_mmc.cycle(cycle);
-          // Find a minimum mean cycle (Hartmann-Orlin algorithm)
-          if (!(ho_mmc.findCycleMean() && ho_mmc.cycleCost() < 0)) break;
-          ho_mmc.findCycle();
-        } else {
-          // Find a minimum mean cycle (Howard algorithm)
-          if (!(hw_tc == HwMmc::OPTIMAL && hw_mmc.cycleCost() < 0)) break;
-          hw_mmc.findCycle();
-        }
-        
+      while (mmc.findCycleMean() && mmc.cycleCost() < 0) {
+        // Find the cycle
+        mmc.findCycle();
+
         // Compute delta value
         Value delta = INF;
@@ -989 +965 @@
       const double LIMIT_FACTOR = 1.0;
       const int MIN_LIMIT = 5;
-      const double HW_ITER_LIMIT_FACTOR = 1.0;
-      const int HW_ITER_LIMIT_MIN_VALUE = 5;
-
-      const int hw_iter_limit =
-          std::max(static_cast<int>(HW_ITER_LIMIT_FACTOR * _node_num),
-                   HW_ITER_LIMIT_MIN_VALUE);
 
       // Contruct auxiliary data vectors
@@ -1168 +1138 @@
           }
         } else {
-          typedef HowardMmc<StaticDigraph, CostArcMap> HwMmc;
-          typedef HartmannOrlinMmc<StaticDigraph, CostArcMap> HoMmc;
+          typedef HowardMmc<StaticDigraph, CostArcMap> MMC;
           typedef typename BellmanFord<StaticDigraph, CostArcMap>
             ::template SetDistMap<CostNodeMap>::Create BF;
 
           // Set epsilon to the minimum cycle mean
-          Cost cycle_cost = 0;
-          int cycle_size = 1;
           buildResidualNetwork();
-          HwMmc hw_mmc(_sgr, _cost_map);
-          if (hw_mmc.findCycleMean(hw_iter_limit) == HwMmc::ITERATION_LIMIT) {
-            // Howard's algorithm reached the iteration limit, start a
-            // strongly polynomial algorithm instead
-            HoMmc ho_mmc(_sgr, _cost_map);
-            ho_mmc.findCycleMean();
-            epsilon = -ho_mmc.cycleMean();
-            cycle_cost = ho_mmc.cycleCost();
-            cycle_size = ho_mmc.cycleSize();
-          } else {
-            // Set epsilon
-            epsilon = -hw_mmc.cycleMean();
-            cycle_cost = hw_mmc.cycleCost();
-            cycle_size = hw_mmc.cycleSize();
-          }
+          MMC mmc(_sgr, _cost_map);
+          mmc.findCycleMean();
+          epsilon = -mmc.cycleMean();
+          Cost cycle_cost = mmc.cycleCost();
+          int cycle_size = mmc.cycleSize();
 
           // Compute feasible potentials for the current epsilon

lemon/howard_mmc.h

@@ -150 +150 @@
     typedef TR Traits;
 
-    /// \brief Constants for the causes of search termination.
-    ///
-    /// Enum type containing constants for the different causes of search
-    /// termination. The \ref findCycleMean() function returns one of
-    /// these values.
-    enum TerminationCause {
-      
-      /// No directed cycle can be found in the digraph.
-      NO_CYCLE = 0,
-    
-      /// Optimal solution (minimum cycle mean) is found.
-      OPTIMAL = 1,
-
-      /// The iteration count limit is reached.
-      ITERATION_LIMIT
-    };
-
   private:
 
@@ -342 +325 @@
     }
 
-    /// \brief Find the minimum cycle mean (or an upper bound).
+    /// \brief Find the minimum cycle mean.
     ///
     /// This function finds the minimum mean cost of the directed
-    /// cycles in the digraph (or an upper bound for it).
-    ///
-    /// By default, the function finds the exact minimum cycle mean,
-    /// but an optional limit can also be specified for the number of
-    /// iterations performed during the search process.
-    /// The return value indicates if the optimal solution is found
-    /// or the iteration limit is reached. In the latter case, an
-    /// approximate solution is provided, which corresponds to a directed
-    /// cycle whose mean cost is relatively small, but not necessarily
-    /// minimal.
-    ///
-    /// \param limit  The maximum allowed number of iterations during
-    /// the search process. Its default value implies that the algorithm 
-    /// runs until it finds the exact optimal solution.
-    ///
-    /// \return The termination cause of the search process.
-    /// For more information, see \ref TerminationCause. 
-    TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max()) {
+    /// cycles in the digraph.
+    ///
+    /// \return \c true if a directed cycle exists in the digraph.
+    bool findCycleMean() {
       // Initialize and find strongly connected components
       init();
@@ -368 +337 @@
 
       // Find the minimum cycle mean in the components
-      int iter_count = 0;
-      bool iter_limit_reached = false;
       for (int comp = 0; comp < _comp_num; ++comp) {
         // Find the minimum mean cycle in the current component
         if (!buildPolicyGraph(comp)) continue;
         while (true) {
-          if (++iter_count > limit) {
-            iter_limit_reached = true;
-            break;
-          }
           findPolicyCycle();
           if (!computeNodeDistances()) break;
         }
-
         // Update the best cycle (global minimum mean cycle)
         if ( _curr_found && (!_best_found ||
@@ -390 +352 @@
           _best_node = _curr_node;
         }
-        
-        if (iter_limit_reached) break;
-      }
-
-      if (iter_limit_reached) {
-        return ITERATION_LIMIT;
-      } else {
-        return _best_found ? OPTIMAL : NO_CYCLE;
-      }
+      }
+      return _best_found;
     }
 

test/min_mean_cycle_test.cc

@@ -111 +111 @@
                  int cost, int size) {
   MMC alg(gr, lm);
-  check(alg.findCycleMean(), "Wrong result");
+  alg.findCycleMean();
   check(alg.cycleMean() == static_cast<double>(cost) / size,
         "Wrong cycle mean");
@@ -211 +211 @@
     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
     checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
-    
-    // Howard with iteration limit
-    HowardMmc<GR, IntArcMap> mmc(gr, l1);
-    check((mmc.findCycleMean(2) == HowardMmc<GR, IntArcMap>::ITERATION_LIMIT),
-      "Wrong termination cause");
-    check((mmc.findCycleMean(4) == HowardMmc<GR, IntArcMap>::OPTIMAL),
-      "Wrong termination cause");
   }