159 } |
159 } |
160 |
160 |
161 private: |
161 private: |
162 |
162 |
163 void activate(const Node& i) { |
163 void activate(const Node& i) { |
164 _active->set(i, true); |
164 (*_active)[i] = true; |
165 |
165 |
166 int bucket = (*_bucket)[i]; |
166 int bucket = (*_bucket)[i]; |
167 |
167 |
168 if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return; |
168 if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return; |
169 //unlace |
169 //unlace |
170 _next->set((*_prev)[i], (*_next)[i]); |
170 (*_next)[(*_prev)[i]] = (*_next)[i]; |
171 if ((*_next)[i] != INVALID) { |
171 if ((*_next)[i] != INVALID) { |
172 _prev->set((*_next)[i], (*_prev)[i]); |
172 (*_prev)[(*_next)[i]] = (*_prev)[i]; |
173 } else { |
173 } else { |
174 _last[bucket] = (*_prev)[i]; |
174 _last[bucket] = (*_prev)[i]; |
175 } |
175 } |
176 //lace |
176 //lace |
177 _next->set(i, _first[bucket]); |
177 (*_next)[i] = _first[bucket]; |
178 _prev->set(_first[bucket], i); |
178 (*_prev)[_first[bucket]] = i; |
179 _prev->set(i, INVALID); |
179 (*_prev)[i] = INVALID; |
180 _first[bucket] = i; |
180 _first[bucket] = i; |
181 } |
181 } |
182 |
182 |
183 void deactivate(const Node& i) { |
183 void deactivate(const Node& i) { |
184 _active->set(i, false); |
184 (*_active)[i] = false; |
185 int bucket = (*_bucket)[i]; |
185 int bucket = (*_bucket)[i]; |
186 |
186 |
187 if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return; |
187 if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return; |
188 |
188 |
189 //unlace |
189 //unlace |
190 _prev->set((*_next)[i], (*_prev)[i]); |
190 (*_prev)[(*_next)[i]] = (*_prev)[i]; |
191 if ((*_prev)[i] != INVALID) { |
191 if ((*_prev)[i] != INVALID) { |
192 _next->set((*_prev)[i], (*_next)[i]); |
192 (*_next)[(*_prev)[i]] = (*_next)[i]; |
193 } else { |
193 } else { |
194 _first[bucket] = (*_next)[i]; |
194 _first[bucket] = (*_next)[i]; |
195 } |
195 } |
196 //lace |
196 //lace |
197 _prev->set(i, _last[bucket]); |
197 (*_prev)[i] = _last[bucket]; |
198 _next->set(_last[bucket], i); |
198 (*_next)[_last[bucket]] = i; |
199 _next->set(i, INVALID); |
199 (*_next)[i] = INVALID; |
200 _last[bucket] = i; |
200 _last[bucket] = i; |
201 } |
201 } |
202 |
202 |
203 void addItem(const Node& i, int bucket) { |
203 void addItem(const Node& i, int bucket) { |
204 (*_bucket)[i] = bucket; |
204 (*_bucket)[i] = bucket; |
205 if (_last[bucket] != INVALID) { |
205 if (_last[bucket] != INVALID) { |
206 _prev->set(i, _last[bucket]); |
206 (*_prev)[i] = _last[bucket]; |
207 _next->set(_last[bucket], i); |
207 (*_next)[_last[bucket]] = i; |
208 _next->set(i, INVALID); |
208 (*_next)[i] = INVALID; |
209 _last[bucket] = i; |
209 _last[bucket] = i; |
210 } else { |
210 } else { |
211 _prev->set(i, INVALID); |
211 (*_prev)[i] = INVALID; |
212 _first[bucket] = i; |
212 _first[bucket] = i; |
213 _next->set(i, INVALID); |
213 (*_next)[i] = INVALID; |
214 _last[bucket] = i; |
214 _last[bucket] = i; |
215 } |
215 } |
216 } |
216 } |
217 |
217 |
218 void findMinCutOut() { |
218 void findMinCutOut() { |
219 |
219 |
220 for (NodeIt n(_graph); n != INVALID; ++n) { |
220 for (NodeIt n(_graph); n != INVALID; ++n) { |
221 _excess->set(n, 0); |
221 (*_excess)[n] = 0; |
222 } |
222 } |
223 |
223 |
224 for (ArcIt a(_graph); a != INVALID; ++a) { |
224 for (ArcIt a(_graph); a != INVALID; ++a) { |
225 _flow->set(a, 0); |
225 (*_flow)[a] = 0; |
226 } |
226 } |
227 |
227 |
228 int bucket_num = 0; |
228 int bucket_num = 0; |
229 std::vector<Node> queue(_node_num); |
229 std::vector<Node> queue(_node_num); |
230 int qfirst = 0, qlast = 0, qsep = 0; |
230 int qfirst = 0, qlast = 0, qsep = 0; |
231 |
231 |
232 { |
232 { |
233 typename Digraph::template NodeMap<bool> reached(_graph, false); |
233 typename Digraph::template NodeMap<bool> reached(_graph, false); |
234 |
234 |
235 reached.set(_source, true); |
235 reached[_source] = true; |
236 bool first_set = true; |
236 bool first_set = true; |
237 |
237 |
238 for (NodeIt t(_graph); t != INVALID; ++t) { |
238 for (NodeIt t(_graph); t != INVALID; ++t) { |
239 if (reached[t]) continue; |
239 if (reached[t]) continue; |
240 _sets.push_front(std::list<int>()); |
240 _sets.push_front(std::list<int>()); |
241 |
241 |
242 queue[qlast++] = t; |
242 queue[qlast++] = t; |
243 reached.set(t, true); |
243 reached[t] = true; |
244 |
244 |
245 while (qfirst != qlast) { |
245 while (qfirst != qlast) { |
246 if (qsep == qfirst) { |
246 if (qsep == qfirst) { |
247 ++bucket_num; |
247 ++bucket_num; |
248 _sets.front().push_front(bucket_num); |
248 _sets.front().push_front(bucket_num); |
255 addItem(n, bucket_num); |
255 addItem(n, bucket_num); |
256 |
256 |
257 for (InArcIt a(_graph, n); a != INVALID; ++a) { |
257 for (InArcIt a(_graph, n); a != INVALID; ++a) { |
258 Node u = _graph.source(a); |
258 Node u = _graph.source(a); |
259 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
259 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
260 reached.set(u, true); |
260 reached[u] = true; |
261 queue[qlast++] = u; |
261 queue[qlast++] = u; |
262 } |
262 } |
263 } |
263 } |
264 } |
264 } |
265 first_set = false; |
265 first_set = false; |
266 } |
266 } |
267 |
267 |
268 ++bucket_num; |
268 ++bucket_num; |
269 _bucket->set(_source, 0); |
269 (*_bucket)[_source] = 0; |
270 _dormant[0] = true; |
270 _dormant[0] = true; |
271 } |
271 } |
272 _source_set->set(_source, true); |
272 (*_source_set)[_source] = true; |
273 |
273 |
274 Node target = _last[_sets.back().back()]; |
274 Node target = _last[_sets.back().back()]; |
275 { |
275 { |
276 for (OutArcIt a(_graph, _source); a != INVALID; ++a) { |
276 for (OutArcIt a(_graph, _source); a != INVALID; ++a) { |
277 if (_tolerance.positive((*_capacity)[a])) { |
277 if (_tolerance.positive((*_capacity)[a])) { |
278 Node u = _graph.target(a); |
278 Node u = _graph.target(a); |
279 _flow->set(a, (*_capacity)[a]); |
279 (*_flow)[a] = (*_capacity)[a]; |
280 _excess->set(u, (*_excess)[u] + (*_capacity)[a]); |
280 (*_excess)[u] += (*_capacity)[a]; |
281 if (!(*_active)[u] && u != _source) { |
281 if (!(*_active)[u] && u != _source) { |
282 activate(u); |
282 activate(u); |
283 } |
283 } |
284 } |
284 } |
285 } |
285 } |
316 if ((*_bucket)[v] == under_bucket) { |
316 if ((*_bucket)[v] == under_bucket) { |
317 if (!(*_active)[v] && v != target) { |
317 if (!(*_active)[v] && v != target) { |
318 activate(v); |
318 activate(v); |
319 } |
319 } |
320 if (!_tolerance.less(rem, excess)) { |
320 if (!_tolerance.less(rem, excess)) { |
321 _flow->set(a, (*_flow)[a] + excess); |
321 (*_flow)[a] += excess; |
322 _excess->set(v, (*_excess)[v] + excess); |
322 (*_excess)[v] += excess; |
323 excess = 0; |
323 excess = 0; |
324 goto no_more_push; |
324 goto no_more_push; |
325 } else { |
325 } else { |
326 excess -= rem; |
326 excess -= rem; |
327 _excess->set(v, (*_excess)[v] + rem); |
327 (*_excess)[v] += rem; |
328 _flow->set(a, (*_capacity)[a]); |
328 (*_flow)[a] = (*_capacity)[a]; |
329 } |
329 } |
330 } else if (next_bucket > (*_bucket)[v]) { |
330 } else if (next_bucket > (*_bucket)[v]) { |
331 next_bucket = (*_bucket)[v]; |
331 next_bucket = (*_bucket)[v]; |
332 } |
332 } |
333 } |
333 } |
340 if ((*_bucket)[v] == under_bucket) { |
340 if ((*_bucket)[v] == under_bucket) { |
341 if (!(*_active)[v] && v != target) { |
341 if (!(*_active)[v] && v != target) { |
342 activate(v); |
342 activate(v); |
343 } |
343 } |
344 if (!_tolerance.less(rem, excess)) { |
344 if (!_tolerance.less(rem, excess)) { |
345 _flow->set(a, (*_flow)[a] - excess); |
345 (*_flow)[a] -= excess; |
346 _excess->set(v, (*_excess)[v] + excess); |
346 (*_excess)[v] += excess; |
347 excess = 0; |
347 excess = 0; |
348 goto no_more_push; |
348 goto no_more_push; |
349 } else { |
349 } else { |
350 excess -= rem; |
350 excess -= rem; |
351 _excess->set(v, (*_excess)[v] + rem); |
351 (*_excess)[v] += rem; |
352 _flow->set(a, 0); |
352 (*_flow)[a] = 0; |
353 } |
353 } |
354 } else if (next_bucket > (*_bucket)[v]) { |
354 } else if (next_bucket > (*_bucket)[v]) { |
355 next_bucket = (*_bucket)[v]; |
355 next_bucket = (*_bucket)[v]; |
356 } |
356 } |
357 } |
357 } |
358 |
358 |
359 no_more_push: |
359 no_more_push: |
360 |
360 |
361 _excess->set(n, excess); |
361 (*_excess)[n] = excess; |
362 |
362 |
363 if (excess != 0) { |
363 if (excess != 0) { |
364 if ((*_next)[n] == INVALID) { |
364 if ((*_next)[n] == INVALID) { |
365 typename std::list<std::list<int> >::iterator new_set = |
365 typename std::list<std::list<int> >::iterator new_set = |
366 _sets.insert(--_sets.end(), std::list<int>()); |
366 _sets.insert(--_sets.end(), std::list<int>()); |
374 !(*_active)[_first[*_highest]]) { |
374 !(*_active)[_first[*_highest]]) { |
375 ++_highest; |
375 ++_highest; |
376 } |
376 } |
377 } else if (next_bucket == _node_num) { |
377 } else if (next_bucket == _node_num) { |
378 _first[(*_bucket)[n]] = (*_next)[n]; |
378 _first[(*_bucket)[n]] = (*_next)[n]; |
379 _prev->set((*_next)[n], INVALID); |
379 (*_prev)[(*_next)[n]] = INVALID; |
380 |
380 |
381 std::list<std::list<int> >::iterator new_set = |
381 std::list<std::list<int> >::iterator new_set = |
382 _sets.insert(--_sets.end(), std::list<int>()); |
382 _sets.insert(--_sets.end(), std::list<int>()); |
383 |
383 |
384 new_set->push_front(bucket_num); |
384 new_set->push_front(bucket_num); |
385 _bucket->set(n, bucket_num); |
385 (*_bucket)[n] = bucket_num; |
386 _first[bucket_num] = _last[bucket_num] = n; |
386 _first[bucket_num] = _last[bucket_num] = n; |
387 _next->set(n, INVALID); |
387 (*_next)[n] = INVALID; |
388 _prev->set(n, INVALID); |
388 (*_prev)[n] = INVALID; |
389 _dormant[bucket_num] = true; |
389 _dormant[bucket_num] = true; |
390 ++bucket_num; |
390 ++bucket_num; |
391 |
391 |
392 while (_highest != _sets.back().end() && |
392 while (_highest != _sets.back().end() && |
393 !(*_active)[_first[*_highest]]) { |
393 !(*_active)[_first[*_highest]]) { |
394 ++_highest; |
394 ++_highest; |
395 } |
395 } |
396 } else { |
396 } else { |
397 _first[*_highest] = (*_next)[n]; |
397 _first[*_highest] = (*_next)[n]; |
398 _prev->set((*_next)[n], INVALID); |
398 (*_prev)[(*_next)[n]] = INVALID; |
399 |
399 |
400 while (next_bucket != *_highest) { |
400 while (next_bucket != *_highest) { |
401 --_highest; |
401 --_highest; |
402 } |
402 } |
403 |
403 |
451 if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) { |
451 if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) { |
452 if ((*_next)[target] == INVALID) { |
452 if ((*_next)[target] == INVALID) { |
453 _last[(*_bucket)[target]] = (*_prev)[target]; |
453 _last[(*_bucket)[target]] = (*_prev)[target]; |
454 new_target = (*_prev)[target]; |
454 new_target = (*_prev)[target]; |
455 } else { |
455 } else { |
456 _prev->set((*_next)[target], (*_prev)[target]); |
456 (*_prev)[(*_next)[target]] = (*_prev)[target]; |
457 new_target = (*_next)[target]; |
457 new_target = (*_next)[target]; |
458 } |
458 } |
459 if ((*_prev)[target] == INVALID) { |
459 if ((*_prev)[target] == INVALID) { |
460 _first[(*_bucket)[target]] = (*_next)[target]; |
460 _first[(*_bucket)[target]] = (*_next)[target]; |
461 } else { |
461 } else { |
462 _next->set((*_prev)[target], (*_next)[target]); |
462 (*_next)[(*_prev)[target]] = (*_next)[target]; |
463 } |
463 } |
464 } else { |
464 } else { |
465 _sets.back().pop_back(); |
465 _sets.back().pop_back(); |
466 if (_sets.back().empty()) { |
466 if (_sets.back().empty()) { |
467 _sets.pop_back(); |
467 _sets.pop_back(); |
473 } |
473 } |
474 } |
474 } |
475 new_target = _last[_sets.back().back()]; |
475 new_target = _last[_sets.back().back()]; |
476 } |
476 } |
477 |
477 |
478 _bucket->set(target, 0); |
478 (*_bucket)[target] = 0; |
479 |
479 |
480 _source_set->set(target, true); |
480 (*_source_set)[target] = true; |
481 for (OutArcIt a(_graph, target); a != INVALID; ++a) { |
481 for (OutArcIt a(_graph, target); a != INVALID; ++a) { |
482 Value rem = (*_capacity)[a] - (*_flow)[a]; |
482 Value rem = (*_capacity)[a] - (*_flow)[a]; |
483 if (!_tolerance.positive(rem)) continue; |
483 if (!_tolerance.positive(rem)) continue; |
484 Node v = _graph.target(a); |
484 Node v = _graph.target(a); |
485 if (!(*_active)[v] && !(*_source_set)[v]) { |
485 if (!(*_active)[v] && !(*_source_set)[v]) { |
486 activate(v); |
486 activate(v); |
487 } |
487 } |
488 _excess->set(v, (*_excess)[v] + rem); |
488 (*_excess)[v] += rem; |
489 _flow->set(a, (*_capacity)[a]); |
489 (*_flow)[a] = (*_capacity)[a]; |
490 } |
490 } |
491 |
491 |
492 for (InArcIt a(_graph, target); a != INVALID; ++a) { |
492 for (InArcIt a(_graph, target); a != INVALID; ++a) { |
493 Value rem = (*_flow)[a]; |
493 Value rem = (*_flow)[a]; |
494 if (!_tolerance.positive(rem)) continue; |
494 if (!_tolerance.positive(rem)) continue; |
495 Node v = _graph.source(a); |
495 Node v = _graph.source(a); |
496 if (!(*_active)[v] && !(*_source_set)[v]) { |
496 if (!(*_active)[v] && !(*_source_set)[v]) { |
497 activate(v); |
497 activate(v); |
498 } |
498 } |
499 _excess->set(v, (*_excess)[v] + rem); |
499 (*_excess)[v] += rem; |
500 _flow->set(a, 0); |
500 (*_flow)[a] = 0; |
501 } |
501 } |
502 |
502 |
503 target = new_target; |
503 target = new_target; |
504 if ((*_active)[target]) { |
504 if ((*_active)[target]) { |
505 deactivate(target); |
505 deactivate(target); |
515 } |
515 } |
516 |
516 |
517 void findMinCutIn() { |
517 void findMinCutIn() { |
518 |
518 |
519 for (NodeIt n(_graph); n != INVALID; ++n) { |
519 for (NodeIt n(_graph); n != INVALID; ++n) { |
520 _excess->set(n, 0); |
520 (*_excess)[n] = 0; |
521 } |
521 } |
522 |
522 |
523 for (ArcIt a(_graph); a != INVALID; ++a) { |
523 for (ArcIt a(_graph); a != INVALID; ++a) { |
524 _flow->set(a, 0); |
524 (*_flow)[a] = 0; |
525 } |
525 } |
526 |
526 |
527 int bucket_num = 0; |
527 int bucket_num = 0; |
528 std::vector<Node> queue(_node_num); |
528 std::vector<Node> queue(_node_num); |
529 int qfirst = 0, qlast = 0, qsep = 0; |
529 int qfirst = 0, qlast = 0, qsep = 0; |
530 |
530 |
531 { |
531 { |
532 typename Digraph::template NodeMap<bool> reached(_graph, false); |
532 typename Digraph::template NodeMap<bool> reached(_graph, false); |
533 |
533 |
534 reached.set(_source, true); |
534 reached[_source] = true; |
535 |
535 |
536 bool first_set = true; |
536 bool first_set = true; |
537 |
537 |
538 for (NodeIt t(_graph); t != INVALID; ++t) { |
538 for (NodeIt t(_graph); t != INVALID; ++t) { |
539 if (reached[t]) continue; |
539 if (reached[t]) continue; |
540 _sets.push_front(std::list<int>()); |
540 _sets.push_front(std::list<int>()); |
541 |
541 |
542 queue[qlast++] = t; |
542 queue[qlast++] = t; |
543 reached.set(t, true); |
543 reached[t] = true; |
544 |
544 |
545 while (qfirst != qlast) { |
545 while (qfirst != qlast) { |
546 if (qsep == qfirst) { |
546 if (qsep == qfirst) { |
547 ++bucket_num; |
547 ++bucket_num; |
548 _sets.front().push_front(bucket_num); |
548 _sets.front().push_front(bucket_num); |
555 addItem(n, bucket_num); |
555 addItem(n, bucket_num); |
556 |
556 |
557 for (OutArcIt a(_graph, n); a != INVALID; ++a) { |
557 for (OutArcIt a(_graph, n); a != INVALID; ++a) { |
558 Node u = _graph.target(a); |
558 Node u = _graph.target(a); |
559 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
559 if (!reached[u] && _tolerance.positive((*_capacity)[a])) { |
560 reached.set(u, true); |
560 reached[u] = true; |
561 queue[qlast++] = u; |
561 queue[qlast++] = u; |
562 } |
562 } |
563 } |
563 } |
564 } |
564 } |
565 first_set = false; |
565 first_set = false; |
566 } |
566 } |
567 |
567 |
568 ++bucket_num; |
568 ++bucket_num; |
569 _bucket->set(_source, 0); |
569 (*_bucket)[_source] = 0; |
570 _dormant[0] = true; |
570 _dormant[0] = true; |
571 } |
571 } |
572 _source_set->set(_source, true); |
572 (*_source_set)[_source] = true; |
573 |
573 |
574 Node target = _last[_sets.back().back()]; |
574 Node target = _last[_sets.back().back()]; |
575 { |
575 { |
576 for (InArcIt a(_graph, _source); a != INVALID; ++a) { |
576 for (InArcIt a(_graph, _source); a != INVALID; ++a) { |
577 if (_tolerance.positive((*_capacity)[a])) { |
577 if (_tolerance.positive((*_capacity)[a])) { |
578 Node u = _graph.source(a); |
578 Node u = _graph.source(a); |
579 _flow->set(a, (*_capacity)[a]); |
579 (*_flow)[a] = (*_capacity)[a]; |
580 _excess->set(u, (*_excess)[u] + (*_capacity)[a]); |
580 (*_excess)[u] += (*_capacity)[a]; |
581 if (!(*_active)[u] && u != _source) { |
581 if (!(*_active)[u] && u != _source) { |
582 activate(u); |
582 activate(u); |
583 } |
583 } |
584 } |
584 } |
585 } |
585 } |
616 if ((*_bucket)[v] == under_bucket) { |
616 if ((*_bucket)[v] == under_bucket) { |
617 if (!(*_active)[v] && v != target) { |
617 if (!(*_active)[v] && v != target) { |
618 activate(v); |
618 activate(v); |
619 } |
619 } |
620 if (!_tolerance.less(rem, excess)) { |
620 if (!_tolerance.less(rem, excess)) { |
621 _flow->set(a, (*_flow)[a] + excess); |
621 (*_flow)[a] += excess; |
622 _excess->set(v, (*_excess)[v] + excess); |
622 (*_excess)[v] += excess; |
623 excess = 0; |
623 excess = 0; |
624 goto no_more_push; |
624 goto no_more_push; |
625 } else { |
625 } else { |
626 excess -= rem; |
626 excess -= rem; |
627 _excess->set(v, (*_excess)[v] + rem); |
627 (*_excess)[v] += rem; |
628 _flow->set(a, (*_capacity)[a]); |
628 (*_flow)[a] = (*_capacity)[a]; |
629 } |
629 } |
630 } else if (next_bucket > (*_bucket)[v]) { |
630 } else if (next_bucket > (*_bucket)[v]) { |
631 next_bucket = (*_bucket)[v]; |
631 next_bucket = (*_bucket)[v]; |
632 } |
632 } |
633 } |
633 } |
640 if ((*_bucket)[v] == under_bucket) { |
640 if ((*_bucket)[v] == under_bucket) { |
641 if (!(*_active)[v] && v != target) { |
641 if (!(*_active)[v] && v != target) { |
642 activate(v); |
642 activate(v); |
643 } |
643 } |
644 if (!_tolerance.less(rem, excess)) { |
644 if (!_tolerance.less(rem, excess)) { |
645 _flow->set(a, (*_flow)[a] - excess); |
645 (*_flow)[a] -= excess; |
646 _excess->set(v, (*_excess)[v] + excess); |
646 (*_excess)[v] += excess; |
647 excess = 0; |
647 excess = 0; |
648 goto no_more_push; |
648 goto no_more_push; |
649 } else { |
649 } else { |
650 excess -= rem; |
650 excess -= rem; |
651 _excess->set(v, (*_excess)[v] + rem); |
651 (*_excess)[v] += rem; |
652 _flow->set(a, 0); |
652 (*_flow)[a] = 0; |
653 } |
653 } |
654 } else if (next_bucket > (*_bucket)[v]) { |
654 } else if (next_bucket > (*_bucket)[v]) { |
655 next_bucket = (*_bucket)[v]; |
655 next_bucket = (*_bucket)[v]; |
656 } |
656 } |
657 } |
657 } |
658 |
658 |
659 no_more_push: |
659 no_more_push: |
660 |
660 |
661 _excess->set(n, excess); |
661 (*_excess)[n] = excess; |
662 |
662 |
663 if (excess != 0) { |
663 if (excess != 0) { |
664 if ((*_next)[n] == INVALID) { |
664 if ((*_next)[n] == INVALID) { |
665 typename std::list<std::list<int> >::iterator new_set = |
665 typename std::list<std::list<int> >::iterator new_set = |
666 _sets.insert(--_sets.end(), std::list<int>()); |
666 _sets.insert(--_sets.end(), std::list<int>()); |
674 !(*_active)[_first[*_highest]]) { |
674 !(*_active)[_first[*_highest]]) { |
675 ++_highest; |
675 ++_highest; |
676 } |
676 } |
677 } else if (next_bucket == _node_num) { |
677 } else if (next_bucket == _node_num) { |
678 _first[(*_bucket)[n]] = (*_next)[n]; |
678 _first[(*_bucket)[n]] = (*_next)[n]; |
679 _prev->set((*_next)[n], INVALID); |
679 (*_prev)[(*_next)[n]] = INVALID; |
680 |
680 |
681 std::list<std::list<int> >::iterator new_set = |
681 std::list<std::list<int> >::iterator new_set = |
682 _sets.insert(--_sets.end(), std::list<int>()); |
682 _sets.insert(--_sets.end(), std::list<int>()); |
683 |
683 |
684 new_set->push_front(bucket_num); |
684 new_set->push_front(bucket_num); |
685 _bucket->set(n, bucket_num); |
685 (*_bucket)[n] = bucket_num; |
686 _first[bucket_num] = _last[bucket_num] = n; |
686 _first[bucket_num] = _last[bucket_num] = n; |
687 _next->set(n, INVALID); |
687 (*_next)[n] = INVALID; |
688 _prev->set(n, INVALID); |
688 (*_prev)[n] = INVALID; |
689 _dormant[bucket_num] = true; |
689 _dormant[bucket_num] = true; |
690 ++bucket_num; |
690 ++bucket_num; |
691 |
691 |
692 while (_highest != _sets.back().end() && |
692 while (_highest != _sets.back().end() && |
693 !(*_active)[_first[*_highest]]) { |
693 !(*_active)[_first[*_highest]]) { |
694 ++_highest; |
694 ++_highest; |
695 } |
695 } |
696 } else { |
696 } else { |
697 _first[*_highest] = (*_next)[n]; |
697 _first[*_highest] = (*_next)[n]; |
698 _prev->set((*_next)[n], INVALID); |
698 (*_prev)[(*_next)[n]] = INVALID; |
699 |
699 |
700 while (next_bucket != *_highest) { |
700 while (next_bucket != *_highest) { |
701 --_highest; |
701 --_highest; |
702 } |
702 } |
703 if (_highest == _sets.back().begin()) { |
703 if (_highest == _sets.back().begin()) { |
750 if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) { |
750 if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) { |
751 if ((*_next)[target] == INVALID) { |
751 if ((*_next)[target] == INVALID) { |
752 _last[(*_bucket)[target]] = (*_prev)[target]; |
752 _last[(*_bucket)[target]] = (*_prev)[target]; |
753 new_target = (*_prev)[target]; |
753 new_target = (*_prev)[target]; |
754 } else { |
754 } else { |
755 _prev->set((*_next)[target], (*_prev)[target]); |
755 (*_prev)[(*_next)[target]] = (*_prev)[target]; |
756 new_target = (*_next)[target]; |
756 new_target = (*_next)[target]; |
757 } |
757 } |
758 if ((*_prev)[target] == INVALID) { |
758 if ((*_prev)[target] == INVALID) { |
759 _first[(*_bucket)[target]] = (*_next)[target]; |
759 _first[(*_bucket)[target]] = (*_next)[target]; |
760 } else { |
760 } else { |
761 _next->set((*_prev)[target], (*_next)[target]); |
761 (*_next)[(*_prev)[target]] = (*_next)[target]; |
762 } |
762 } |
763 } else { |
763 } else { |
764 _sets.back().pop_back(); |
764 _sets.back().pop_back(); |
765 if (_sets.back().empty()) { |
765 if (_sets.back().empty()) { |
766 _sets.pop_back(); |
766 _sets.pop_back(); |
772 } |
772 } |
773 } |
773 } |
774 new_target = _last[_sets.back().back()]; |
774 new_target = _last[_sets.back().back()]; |
775 } |
775 } |
776 |
776 |
777 _bucket->set(target, 0); |
777 (*_bucket)[target] = 0; |
778 |
778 |
779 _source_set->set(target, true); |
779 (*_source_set)[target] = true; |
780 for (InArcIt a(_graph, target); a != INVALID; ++a) { |
780 for (InArcIt a(_graph, target); a != INVALID; ++a) { |
781 Value rem = (*_capacity)[a] - (*_flow)[a]; |
781 Value rem = (*_capacity)[a] - (*_flow)[a]; |
782 if (!_tolerance.positive(rem)) continue; |
782 if (!_tolerance.positive(rem)) continue; |
783 Node v = _graph.source(a); |
783 Node v = _graph.source(a); |
784 if (!(*_active)[v] && !(*_source_set)[v]) { |
784 if (!(*_active)[v] && !(*_source_set)[v]) { |
785 activate(v); |
785 activate(v); |
786 } |
786 } |
787 _excess->set(v, (*_excess)[v] + rem); |
787 (*_excess)[v] += rem; |
788 _flow->set(a, (*_capacity)[a]); |
788 (*_flow)[a] = (*_capacity)[a]; |
789 } |
789 } |
790 |
790 |
791 for (OutArcIt a(_graph, target); a != INVALID; ++a) { |
791 for (OutArcIt a(_graph, target); a != INVALID; ++a) { |
792 Value rem = (*_flow)[a]; |
792 Value rem = (*_flow)[a]; |
793 if (!_tolerance.positive(rem)) continue; |
793 if (!_tolerance.positive(rem)) continue; |
794 Node v = _graph.target(a); |
794 Node v = _graph.target(a); |
795 if (!(*_active)[v] && !(*_source_set)[v]) { |
795 if (!(*_active)[v] && !(*_source_set)[v]) { |
796 activate(v); |
796 activate(v); |
797 } |
797 } |
798 _excess->set(v, (*_excess)[v] + rem); |
798 (*_excess)[v] += rem; |
799 _flow->set(a, 0); |
799 (*_flow)[a] = 0; |
800 } |
800 } |
801 |
801 |
802 target = new_target; |
802 target = new_target; |
803 if ((*_active)[target]) { |
803 if ((*_active)[target]) { |
804 deactivate(target); |
804 deactivate(target); |