1.1 --- a/lemon/howard_mmc.h	Thu Nov 08 09:07:41 2012 +0100
     1.2 +++ b/lemon/howard_mmc.h	Thu Nov 15 07:05:29 2012 +0100
     1.3 @@ -149,6 +149,23 @@
     1.4      /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm
     1.5      typedef TR Traits;
     1.6  
     1.7 +    /// \brief Constants for the causes of search termination.
     1.8 +    ///
     1.9 +    /// Enum type containing constants for the different causes of search
    1.10 +    /// termination. The \ref findCycleMean() function returns one of
    1.11 +    /// these values.
    1.12 +    enum TerminationCause {
    1.13 +      
    1.14 +      /// No directed cycle can be found in the digraph.
    1.15 +      NO_CYCLE = 0,
    1.16 +    
    1.17 +      /// Optimal solution (minimum cycle mean) is found.
    1.18 +      OPTIMAL = 1,
    1.19 +
    1.20 +      /// The iteration count limit is reached.
    1.21 +      ITERATION_LIMIT
    1.22 +    };
    1.23 +
    1.24    private:
    1.25  
    1.26      TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
    1.27 @@ -324,25 +341,46 @@
    1.28        return findCycleMean() && findCycle();
    1.29      }
    1.30  
    1.31 -    /// \brief Find the minimum cycle mean.
    1.32 +    /// \brief Find the minimum cycle mean (or an upper bound).
    1.33      ///
    1.34      /// This function finds the minimum mean cost of the directed
    1.35 -    /// cycles in the digraph.
    1.36 +    /// cycles in the digraph (or an upper bound for it).
    1.37      ///
    1.38 -    /// \return \c true if a directed cycle exists in the digraph.
    1.39 -    bool findCycleMean() {
    1.40 +    /// By default, the function finds the exact minimum cycle mean,
    1.41 +    /// but an optional limit can also be specified for the number of
    1.42 +    /// iterations performed during the search process.
    1.43 +    /// The return value indicates if the optimal solution is found
    1.44 +    /// or the iteration limit is reached. In the latter case, an
    1.45 +    /// approximate solution is provided, which corresponds to a directed
    1.46 +    /// cycle whose mean cost is relatively small, but not necessarily
    1.47 +    /// minimal.
    1.48 +    ///
    1.49 +    /// \param limit  The maximum allowed number of iterations during
    1.50 +    /// the search process. Its default value implies that the algorithm 
    1.51 +    /// runs until it finds the exact optimal solution.
    1.52 +    ///
    1.53 +    /// \return The termination cause of the search process.
    1.54 +    /// For more information, see \ref TerminationCause. 
    1.55 +    TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max()) {
    1.56        // Initialize and find strongly connected components
    1.57        init();
    1.58        findComponents();
    1.59  
    1.60        // Find the minimum cycle mean in the components
    1.61 +      int iter_count = 0;
    1.62 +      bool iter_limit_reached = false;
    1.63        for (int comp = 0; comp < _comp_num; ++comp) {
    1.64          // Find the minimum mean cycle in the current component
    1.65          if (!buildPolicyGraph(comp)) continue;
    1.66          while (true) {
    1.67 +          if (++iter_count > limit) {
    1.68 +            iter_limit_reached = true;
    1.69 +            break;
    1.70 +          }
    1.71            findPolicyCycle();
    1.72            if (!computeNodeDistances()) break;
    1.73          }
    1.74 +
    1.75          // Update the best cycle (global minimum mean cycle)
    1.76          if ( _curr_found && (!_best_found ||
    1.77               _curr_cost * _best_size < _best_cost * _curr_size) ) {
    1.78 @@ -351,8 +389,15 @@
    1.79            _best_size = _curr_size;
    1.80            _best_node = _curr_node;
    1.81          }
    1.82 +        
    1.83 +        if (iter_limit_reached) break;
    1.84        }
    1.85 -      return _best_found;
    1.86 +
    1.87 +      if (iter_limit_reached) {
    1.88 +        return ITERATION_LIMIT;
    1.89 +      } else {
    1.90 +        return _best_found ? OPTIMAL : NO_CYCLE;
    1.91 +      }
    1.92      }
    1.93  
    1.94      /// \brief Find a minimum mean directed cycle.

     2.1 --- a/test/min_mean_cycle_test.cc	Thu Nov 08 09:07:41 2012 +0100
     2.2 +++ b/test/min_mean_cycle_test.cc	Thu Nov 15 07:05:29 2012 +0100
     2.3 @@ -110,7 +110,7 @@
     2.4                   const SmartDigraph::ArcMap<int>& cm,
     2.5                   int cost, int size) {
     2.6    MMC alg(gr, lm);
     2.7 -  alg.findCycleMean();
     2.8 +  check(alg.findCycleMean(), "Wrong result");
     2.9    check(alg.cycleMean() == static_cast<double>(cost) / size,
    2.10          "Wrong cycle mean");
    2.11    alg.findCycle();
    2.12 @@ -210,6 +210,13 @@
    2.13      checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l2, c2,  5, 2);
    2.14      checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3,  0, 1);
    2.15      checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, -1, 1);
    2.16 +    
    2.17 +    // Howard with iteration limit
    2.18 +    HowardMmc<GR, IntArcMap> mmc(gr, l1);
    2.19 +    check((mmc.findCycleMean(2) == HowardMmc<GR, IntArcMap>::ITERATION_LIMIT),
    2.20 +      "Wrong termination cause");
    2.21 +    check((mmc.findCycleMean(4) == HowardMmc<GR, IntArcMap>::OPTIMAL),
    2.22 +      "Wrong termination cause");
    2.23    }
    2.24  
    2.25    return 0;