1.1 --- a/lemon/howard_mmc.h Mon Jul 16 16:21:40 2018 +0200
1.2 +++ b/lemon/howard_mmc.h Wed Oct 17 19:14:07 2018 +0200
1.3 @@ -2,7 +2,7 @@
1.4 *
1.5 * This file is a part of LEMON, a generic C++ optimization library.
1.6 *
1.7 - * Copyright (C) 2003-2010
1.8 + * Copyright (C) 2003-2013
1.9 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 *
1.12 @@ -98,7 +98,7 @@
1.13 ///
1.14 /// This class implements Howard's policy iteration algorithm for finding
1.15 /// a directed cycle of minimum mean cost in a digraph
1.16 - /// \ref amo93networkflows, \ref dasdan98minmeancycle.
1.17 + /// \cite dasdan98minmeancycle, \cite dasdan04experimental.
1.18 /// This class provides the most efficient algorithm for the
1.19 /// minimum mean cycle problem, though the best known theoretical
1.20 /// bound on its running time is exponential.
1.21 @@ -142,13 +142,30 @@
1.22 /// \brief The path type of the found cycles
1.23 ///
1.24 /// The path type of the found cycles.
1.25 - /// Using the \ref HowardMmcDefaultTraits "default traits class",
1.26 + /// Using the \ref lemon::HowardMmcDefaultTraits "default traits class",
1.27 /// it is \ref lemon::Path "Path<Digraph>".
1.28 typedef typename TR::Path Path;
1.29
1.30 - /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm
1.31 + /// The \ref lemon::HowardMmcDefaultTraits "traits class" of the algorithm
1.32 typedef TR Traits;
1.33
1.34 + /// \brief Constants for the causes of search termination.
1.35 + ///
1.36 + /// Enum type containing constants for the different causes of search
1.37 + /// termination. The \ref findCycleMean() function returns one of
1.38 + /// these values.
1.39 + enum TerminationCause {
1.40 +
1.41 + /// No directed cycle can be found in the digraph.
1.42 + NO_CYCLE = 0,
1.43 +
1.44 + /// Optimal solution (minimum cycle mean) is found.
1.45 + OPTIMAL = 1,
1.46 +
1.47 + /// The iteration count limit is reached.
1.48 + ITERATION_LIMIT
1.49 + };
1.50 +
1.51 private:
1.52
1.53 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.54 @@ -265,8 +282,8 @@
1.55 /// found cycle.
1.56 ///
1.57 /// If you don't call this function before calling \ref run() or
1.58 - /// \ref findCycleMean(), it will allocate a local \ref Path "path"
1.59 - /// structure. The destuctor deallocates this automatically
1.60 + /// \ref findCycleMean(), a local \ref Path "path" structure
1.61 + /// will be allocated. The destuctor deallocates this automatically
1.62 /// allocated object, of course.
1.63 ///
1.64 /// \note The algorithm calls only the \ref lemon::Path::addBack()
1.65 @@ -324,25 +341,47 @@
1.66 return findCycleMean() && findCycle();
1.67 }
1.68
1.69 - /// \brief Find the minimum cycle mean.
1.70 + /// \brief Find the minimum cycle mean (or an upper bound).
1.71 ///
1.72 /// This function finds the minimum mean cost of the directed
1.73 - /// cycles in the digraph.
1.74 + /// cycles in the digraph (or an upper bound for it).
1.75 ///
1.76 - /// \return \c true if a directed cycle exists in the digraph.
1.77 - bool findCycleMean() {
1.78 + /// By default, the function finds the exact minimum cycle mean,
1.79 + /// but an optional limit can also be specified for the number of
1.80 + /// iterations performed during the search process.
1.81 + /// The return value indicates if the optimal solution is found
1.82 + /// or the iteration limit is reached. In the latter case, an
1.83 + /// approximate solution is provided, which corresponds to a directed
1.84 + /// cycle whose mean cost is relatively small, but not necessarily
1.85 + /// minimal.
1.86 + ///
1.87 + /// \param limit The maximum allowed number of iterations during
1.88 + /// the search process. Its default value implies that the algorithm
1.89 + /// runs until it finds the exact optimal solution.
1.90 + ///
1.91 + /// \return The termination cause of the search process.
1.92 + /// For more information, see \ref TerminationCause.
1.93 + TerminationCause findCycleMean(int limit =
1.94 + std::numeric_limits<int>::max()) {
1.95 // Initialize and find strongly connected components
1.96 init();
1.97 findComponents();
1.98
1.99 // Find the minimum cycle mean in the components
1.100 + int iter_count = 0;
1.101 + bool iter_limit_reached = false;
1.102 for (int comp = 0; comp < _comp_num; ++comp) {
1.103 // Find the minimum mean cycle in the current component
1.104 if (!buildPolicyGraph(comp)) continue;
1.105 while (true) {
1.106 + if (++iter_count > limit) {
1.107 + iter_limit_reached = true;
1.108 + break;
1.109 + }
1.110 findPolicyCycle();
1.111 if (!computeNodeDistances()) break;
1.112 }
1.113 +
1.114 // Update the best cycle (global minimum mean cycle)
1.115 if ( _curr_found && (!_best_found ||
1.116 _curr_cost * _best_size < _best_cost * _curr_size) ) {
1.117 @@ -351,8 +390,15 @@
1.118 _best_size = _curr_size;
1.119 _best_node = _curr_node;
1.120 }
1.121 +
1.122 + if (iter_limit_reached) break;
1.123 }
1.124 - return _best_found;
1.125 +
1.126 + if (iter_limit_reached) {
1.127 + return ITERATION_LIMIT;
1.128 + } else {
1.129 + return _best_found ? OPTIMAL : NO_CYCLE;
1.130 + }
1.131 }
1.132
1.133 /// \brief Find a minimum mean directed cycle.