147 typedef typename TR::Path Path; |
147 typedef typename TR::Path Path; |
148 |
148 |
149 /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm |
149 /// The \ref HowardMmcDefaultTraits "traits class" of the algorithm |
150 typedef TR Traits; |
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 private: |
169 private: |
153 |
170 |
154 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
171 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
155 |
172 |
156 // The digraph the algorithm runs on |
173 // The digraph the algorithm runs on |
322 /// \endcode |
339 /// \endcode |
323 bool run() { |
340 bool run() { |
324 return findCycleMean() && findCycle(); |
341 return findCycleMean() && findCycle(); |
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 /// This function finds the minimum mean cost of the directed |
346 /// This function finds the minimum mean cost of the directed |
330 /// cycles in the digraph. |
347 /// cycles in the digraph (or an upper bound for it). |
331 /// |
348 /// |
332 /// \return \c true if a directed cycle exists in the digraph. |
349 /// By default, the function finds the exact minimum cycle mean, |
333 bool findCycleMean() { |
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 // Initialize and find strongly connected components |
365 // Initialize and find strongly connected components |
335 init(); |
366 init(); |
336 findComponents(); |
367 findComponents(); |
337 |
368 |
338 // Find the minimum cycle mean in the components |
369 // Find the minimum cycle mean in the components |
|
370 int iter_count = 0; |
|
371 bool iter_limit_reached = false; |
339 for (int comp = 0; comp < _comp_num; ++comp) { |
372 for (int comp = 0; comp < _comp_num; ++comp) { |
340 // Find the minimum mean cycle in the current component |
373 // Find the minimum mean cycle in the current component |
341 if (!buildPolicyGraph(comp)) continue; |
374 if (!buildPolicyGraph(comp)) continue; |
342 while (true) { |
375 while (true) { |
|
376 if (++iter_count > limit) { |
|
377 iter_limit_reached = true; |
|
378 break; |
|
379 } |
343 findPolicyCycle(); |
380 findPolicyCycle(); |
344 if (!computeNodeDistances()) break; |
381 if (!computeNodeDistances()) break; |
345 } |
382 } |
|
383 |
346 // Update the best cycle (global minimum mean cycle) |
384 // Update the best cycle (global minimum mean cycle) |
347 if ( _curr_found && (!_best_found || |
385 if ( _curr_found && (!_best_found || |
348 _curr_cost * _best_size < _best_cost * _curr_size) ) { |
386 _curr_cost * _best_size < _best_cost * _curr_size) ) { |
349 _best_found = true; |
387 _best_found = true; |
350 _best_cost = _curr_cost; |
388 _best_cost = _curr_cost; |
351 _best_size = _curr_size; |
389 _best_size = _curr_size; |
352 _best_node = _curr_node; |
390 _best_node = _curr_node; |
353 } |
391 } |
354 } |
392 |
355 return _best_found; |
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 |
358 /// \brief Find a minimum mean directed cycle. |
403 /// \brief Find a minimum mean directed cycle. |
359 /// |
404 /// |
360 /// This function finds a directed cycle of minimum mean cost |
405 /// This function finds a directed cycle of minimum mean cost |