# Changeset 1178:21a9f829ab68 in lemon

Ignore:
Timestamp:
11/15/12 07:05:29 (7 years ago)
Branch:
default
Phase:
public
Message:

Optional iteration limit in HowardMmc? (#438)

Files:
2 edited

Unmodified
Added
Removed
• ## lemon/howard_mmc.h

 r1164 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: } /// \brief Find the minimum cycle mean. /// \brief Find the minimum cycle mean (or an upper bound). /// /// This function finds the minimum mean cost of the directed /// cycles in the digraph. /// /// \return \c true if a directed cycle exists in the digraph. bool findCycleMean() { /// 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::max()) { // Initialize and find strongly connected components init(); // 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 || _best_node = _curr_node; } } return _best_found; if (iter_limit_reached) break; } if (iter_limit_reached) { return ITERATION_LIMIT; } else { return _best_found ? OPTIMAL : NO_CYCLE; } }
• ## test/min_mean_cycle_test.cc

 r956 int cost, int size) { MMC alg(gr, lm); alg.findCycleMean(); check(alg.findCycleMean(), "Wrong result"); check(alg.cycleMean() == static_cast(cost) / size, "Wrong cycle mean"); checkMmcAlg >(gr, l3, c3,  0, 1); checkMmcAlg >(gr, l4, c4, -1, 1); // Howard with iteration limit HowardMmc mmc(gr, l1); check((mmc.findCycleMean(2) == HowardMmc::ITERATION_LIMIT), "Wrong termination cause"); check((mmc.findCycleMean(4) == HowardMmc::OPTIMAL), "Wrong termination cause"); }
Note: See TracChangeset for help on using the changeset viewer.