Changeset 1178:21a9f829ab68 in lemon
 Timestamp:
 11/15/12 07:05:29 (9 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/howard_mmc.h
r1164 r1178 150 150 typedef TR Traits; 151 151 152 /// \brief Constants for the causes of search termination. 153 /// 154 /// Enum type containing constants for the different causes of search 155 /// termination. The \ref findCycleMean() function returns one of 156 /// these values. 157 enum TerminationCause { 158 159 /// No directed cycle can be found in the digraph. 160 NO_CYCLE = 0, 161 162 /// Optimal solution (minimum cycle mean) is found. 163 OPTIMAL = 1, 164 165 /// The iteration count limit is reached. 166 ITERATION_LIMIT 167 }; 168 152 169 private: 153 170 … … 325 342 } 326 343 327 /// \brief Find the minimum cycle mean .344 /// \brief Find the minimum cycle mean (or an upper bound). 328 345 /// 329 346 /// This function finds the minimum mean cost of the directed 330 /// cycles in the digraph. 331 /// 332 /// \return \c true if a directed cycle exists in the digraph. 333 bool findCycleMean() { 347 /// cycles in the digraph (or an upper bound for it). 348 /// 349 /// By default, the function finds the exact minimum cycle mean, 350 /// but an optional limit can also be specified for the number of 351 /// iterations performed during the search process. 352 /// The return value indicates if the optimal solution is found 353 /// or the iteration limit is reached. In the latter case, an 354 /// approximate solution is provided, which corresponds to a directed 355 /// cycle whose mean cost is relatively small, but not necessarily 356 /// minimal. 357 /// 358 /// \param limit The maximum allowed number of iterations during 359 /// the search process. Its default value implies that the algorithm 360 /// runs until it finds the exact optimal solution. 361 /// 362 /// \return The termination cause of the search process. 363 /// For more information, see \ref TerminationCause. 364 TerminationCause findCycleMean(int limit = std::numeric_limits<int>::max()) { 334 365 // Initialize and find strongly connected components 335 366 init(); … … 337 368 338 369 // Find the minimum cycle mean in the components 370 int iter_count = 0; 371 bool iter_limit_reached = false; 339 372 for (int comp = 0; comp < _comp_num; ++comp) { 340 373 // Find the minimum mean cycle in the current component 341 374 if (!buildPolicyGraph(comp)) continue; 342 375 while (true) { 376 if (++iter_count > limit) { 377 iter_limit_reached = true; 378 break; 379 } 343 380 findPolicyCycle(); 344 381 if (!computeNodeDistances()) break; 345 382 } 383 346 384 // Update the best cycle (global minimum mean cycle) 347 385 if ( _curr_found && (!_best_found  … … 352 390 _best_node = _curr_node; 353 391 } 354 } 355 return _best_found; 392 393 if (iter_limit_reached) break; 394 } 395 396 if (iter_limit_reached) { 397 return ITERATION_LIMIT; 398 } else { 399 return _best_found ? OPTIMAL : NO_CYCLE; 400 } 356 401 } 357 402 
test/min_mean_cycle_test.cc
r956 r1178 111 111 int cost, int size) { 112 112 MMC alg(gr, lm); 113 alg.findCycleMean();113 check(alg.findCycleMean(), "Wrong result"); 114 114 check(alg.cycleMean() == static_cast<double>(cost) / size, 115 115 "Wrong cycle mean"); … … 211 211 checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l3, c3, 0, 1); 212 212 checkMmcAlg<HowardMmc<GR, IntArcMap> >(gr, l4, c4, 1, 1); 213 214 // Howard with iteration limit 215 HowardMmc<GR, IntArcMap> mmc(gr, l1); 216 check((mmc.findCycleMean(2) == HowardMmc<GR, IntArcMap>::ITERATION_LIMIT), 217 "Wrong termination cause"); 218 check((mmc.findCycleMean(4) == HowardMmc<GR, IntArcMap>::OPTIMAL), 219 "Wrong termination cause"); 213 220 } 214 221
Note: See TracChangeset
for help on using the changeset viewer.