228 /// |
231 /// |
229 /// \param digraph The digraph the algorithm runs on. |
232 /// \param digraph The digraph the algorithm runs on. |
230 /// \param length The lengths (costs) of the arcs. |
233 /// \param length The lengths (costs) of the arcs. |
231 Howard( const Digraph &digraph, |
234 Howard( const Digraph &digraph, |
232 const LengthMap &length ) : |
235 const LengthMap &length ) : |
233 _gr(digraph), _length(length), _cycle_path(NULL), _local_path(false), |
236 _gr(digraph), _length(length), _best_found(false), |
|
237 _best_length(0), _best_size(1), _cycle_path(NULL), _local_path(false), |
234 _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph), |
238 _policy(digraph), _reached(digraph), _level(digraph), _dist(digraph), |
235 _comp(digraph), _in_arcs(digraph) |
239 _comp(digraph), _in_arcs(digraph), |
|
240 INF(std::numeric_limits<LargeValue>::has_infinity ? |
|
241 std::numeric_limits<LargeValue>::infinity() : |
|
242 std::numeric_limits<LargeValue>::max()) |
236 {} |
243 {} |
237 |
244 |
238 /// Destructor. |
245 /// Destructor. |
239 ~Howard() { |
246 ~Howard() { |
240 if (_local_path) delete _cycle_path; |
247 if (_local_path) delete _cycle_path; |
305 while (true) { |
312 while (true) { |
306 findPolicyCycle(); |
313 findPolicyCycle(); |
307 if (!computeNodeDistances()) break; |
314 if (!computeNodeDistances()) break; |
308 } |
315 } |
309 // Update the best cycle (global minimum mean cycle) |
316 // Update the best cycle (global minimum mean cycle) |
310 if ( !_best_found || (_curr_found && |
317 if ( _curr_found && (!_best_found || |
311 _curr_length * _best_size < _best_length * _curr_size) ) { |
318 _curr_length * _best_size < _best_length * _curr_size) ) { |
312 _best_found = true; |
319 _best_found = true; |
313 _best_length = _curr_length; |
320 _best_length = _curr_length; |
314 _best_size = _curr_size; |
321 _best_size = _curr_size; |
315 _best_node = _curr_node; |
322 _best_node = _curr_node; |
444 if (_nodes->size() < 1 || |
451 if (_nodes->size() < 1 || |
445 (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) { |
452 (_nodes->size() == 1 && _in_arcs[(*_nodes)[0]].size() == 0)) { |
446 return false; |
453 return false; |
447 } |
454 } |
448 for (int i = 0; i < int(_nodes->size()); ++i) { |
455 for (int i = 0; i < int(_nodes->size()); ++i) { |
449 _dist[(*_nodes)[i]] = std::numeric_limits<LargeValue>::max(); |
456 _dist[(*_nodes)[i]] = INF; |
450 } |
457 } |
451 Node u, v; |
458 Node u, v; |
452 Arc e; |
459 Arc e; |
453 for (int i = 0; i < int(_nodes->size()); ++i) { |
460 for (int i = 0; i < int(_nodes->size()); ++i) { |
454 v = (*_nodes)[i]; |
461 v = (*_nodes)[i]; |