146 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
146 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
147 |
147 |
148 // Data sturcture for path data |
148 // Data sturcture for path data |
149 struct PathData |
149 struct PathData |
150 { |
150 { |
151 bool found; |
|
152 LargeValue dist; |
151 LargeValue dist; |
153 Arc pred; |
152 Arc pred; |
154 PathData(bool f = false, LargeValue d = 0, Arc p = INVALID) : |
153 PathData(LargeValue d, Arc p = INVALID) : |
155 found(f), dist(d), pred(p) {} |
154 dist(d), pred(p) {} |
156 }; |
155 }; |
157 |
156 |
158 typedef typename Digraph::template NodeMap<std::vector<PathData> > |
157 typedef typename Digraph::template NodeMap<std::vector<PathData> > |
159 PathDataNodeMap; |
158 PathDataNodeMap; |
160 |
159 |
184 PathDataNodeMap _data; |
183 PathDataNodeMap _data; |
185 // The processed nodes in the last round |
184 // The processed nodes in the last round |
186 std::vector<Node> _process; |
185 std::vector<Node> _process; |
187 |
186 |
188 Tolerance _tolerance; |
187 Tolerance _tolerance; |
|
188 |
|
189 // Infinite constant |
|
190 const LargeValue INF; |
189 |
191 |
190 public: |
192 public: |
191 |
193 |
192 /// \name Named Template Parameters |
194 /// \name Named Template Parameters |
193 /// @{ |
195 /// @{ |
239 /// \param length The lengths (costs) of the arcs. |
241 /// \param length The lengths (costs) of the arcs. |
240 Karp( const Digraph &digraph, |
242 Karp( const Digraph &digraph, |
241 const LengthMap &length ) : |
243 const LengthMap &length ) : |
242 _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph), |
244 _gr(digraph), _length(length), _comp(digraph), _out_arcs(digraph), |
243 _cycle_length(0), _cycle_size(1), _cycle_node(INVALID), |
245 _cycle_length(0), _cycle_size(1), _cycle_node(INVALID), |
244 _cycle_path(NULL), _local_path(false), _data(digraph) |
246 _cycle_path(NULL), _local_path(false), _data(digraph), |
|
247 INF(std::numeric_limits<LargeValue>::has_infinity ? |
|
248 std::numeric_limits<LargeValue>::infinity() : |
|
249 std::numeric_limits<LargeValue>::max()) |
245 {} |
250 {} |
246 |
251 |
247 /// Destructor. |
252 /// Destructor. |
248 ~Karp() { |
253 ~Karp() { |
249 if (_local_path) delete _cycle_path; |
254 if (_local_path) delete _cycle_path; |
456 int n = _nodes->size(); |
461 int n = _nodes->size(); |
457 if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) { |
462 if (n < 1 || (n == 1 && _out_arcs[(*_nodes)[0]].size() == 0)) { |
458 return false; |
463 return false; |
459 } |
464 } |
460 for (int i = 0; i < n; ++i) { |
465 for (int i = 0; i < n; ++i) { |
461 _data[(*_nodes)[i]].resize(n + 1); |
466 _data[(*_nodes)[i]].resize(n + 1, PathData(INF)); |
462 } |
467 } |
463 return true; |
468 return true; |
464 } |
469 } |
465 |
470 |
466 // Process all rounds of computing path data for the current component. |
471 // Process all rounds of computing path data for the current component. |
467 // _data[v][k] is the length of a shortest directed walk from the root |
472 // _data[v][k] is the length of a shortest directed walk from the root |
468 // node to node v containing exactly k arcs. |
473 // node to node v containing exactly k arcs. |
469 void processRounds() { |
474 void processRounds() { |
470 Node start = (*_nodes)[0]; |
475 Node start = (*_nodes)[0]; |
471 _data[start][0] = PathData(true, 0); |
476 _data[start][0] = PathData(0); |
472 _process.clear(); |
477 _process.clear(); |
473 _process.push_back(start); |
478 _process.push_back(start); |
474 |
479 |
475 int k, n = _nodes->size(); |
480 int k, n = _nodes->size(); |
476 for (k = 1; k <= n && int(_process.size()) < n; ++k) { |
481 for (k = 1; k <= n && int(_process.size()) < n; ++k) { |
491 u = _process[i]; |
496 u = _process[i]; |
492 for (int j = 0; j < int(_out_arcs[u].size()); ++j) { |
497 for (int j = 0; j < int(_out_arcs[u].size()); ++j) { |
493 e = _out_arcs[u][j]; |
498 e = _out_arcs[u][j]; |
494 v = _gr.target(e); |
499 v = _gr.target(e); |
495 d = _data[u][k-1].dist + _length[e]; |
500 d = _data[u][k-1].dist + _length[e]; |
496 if (!_data[v][k].found) { |
501 if (_tolerance.less(d, _data[v][k].dist)) { |
497 next.push_back(v); |
502 if (_data[v][k].dist == INF) next.push_back(v); |
498 _data[v][k] = PathData(true, _data[u][k-1].dist + _length[e], e); |
503 _data[v][k] = PathData(d, e); |
499 } |
|
500 else if (_tolerance.less(d, _data[v][k].dist)) { |
|
501 _data[v][k] = PathData(true, d, e); |
|
502 } |
504 } |
503 } |
505 } |
504 } |
506 } |
505 _process.swap(next); |
507 _process.swap(next); |
506 } |
508 } |
514 u = (*_nodes)[i]; |
516 u = (*_nodes)[i]; |
515 for (int j = 0; j < int(_out_arcs[u].size()); ++j) { |
517 for (int j = 0; j < int(_out_arcs[u].size()); ++j) { |
516 e = _out_arcs[u][j]; |
518 e = _out_arcs[u][j]; |
517 v = _gr.target(e); |
519 v = _gr.target(e); |
518 d = _data[u][k-1].dist + _length[e]; |
520 d = _data[u][k-1].dist + _length[e]; |
519 if (!_data[v][k].found || _tolerance.less(d, _data[v][k].dist)) { |
521 if (_tolerance.less(d, _data[v][k].dist)) { |
520 _data[v][k] = PathData(true, d, e); |
522 _data[v][k] = PathData(d, e); |
521 } |
523 } |
522 } |
524 } |
523 } |
525 } |
524 } |
526 } |
525 |
527 |
526 // Update the minimum cycle mean |
528 // Update the minimum cycle mean |
527 void updateMinMean() { |
529 void updateMinMean() { |
528 int n = _nodes->size(); |
530 int n = _nodes->size(); |
529 for (int i = 0; i < n; ++i) { |
531 for (int i = 0; i < n; ++i) { |
530 Node u = (*_nodes)[i]; |
532 Node u = (*_nodes)[i]; |
531 if (!_data[u][n].found) continue; |
533 if (_data[u][n].dist == INF) continue; |
532 LargeValue length, max_length = 0; |
534 LargeValue length, max_length = 0; |
533 int size, max_size = 1; |
535 int size, max_size = 1; |
534 bool found_curr = false; |
536 bool found_curr = false; |
535 for (int k = 0; k < n; ++k) { |
537 for (int k = 0; k < n; ++k) { |
536 if (!_data[u][k].found) continue; |
538 if (_data[u][k].dist == INF) continue; |
537 length = _data[u][n].dist - _data[u][k].dist; |
539 length = _data[u][n].dist - _data[u][k].dist; |
538 size = n - k; |
540 size = n - k; |
539 if (!found_curr || length * max_size > max_length * size) { |
541 if (!found_curr || length * max_size > max_length * size) { |
540 found_curr = true; |
542 found_curr = true; |
541 max_length = length; |
543 max_length = length; |