equal
deleted
inserted
replaced
19 #ifndef LEMON_HAO_ORLIN_H |
19 #ifndef LEMON_HAO_ORLIN_H |
20 #define LEMON_HAO_ORLIN_H |
20 #define LEMON_HAO_ORLIN_H |
21 |
21 |
22 #include <vector> |
22 #include <vector> |
23 #include <list> |
23 #include <list> |
24 #include <ext/hash_set> |
|
25 #include <limits> |
24 #include <limits> |
26 |
25 |
27 #include <lemon/maps.h> |
26 #include <lemon/maps.h> |
28 #include <lemon/graph_utils.h> |
27 #include <lemon/graph_utils.h> |
29 #include <lemon/graph_adaptor.h> |
28 #include <lemon/tolerance.h> |
30 #include <lemon/iterable_maps.h> |
|
31 |
29 |
32 /// \file |
30 /// \file |
33 /// \ingroup min_cut |
31 /// \ingroup min_cut |
34 /// \brief Implementation of the Hao-Orlin algorithm. |
32 /// \brief Implementation of the Hao-Orlin algorithm. |
35 /// |
33 /// |
291 if (_tolerance.positive((*_capacity)[e])) { |
289 if (_tolerance.positive((*_capacity)[e])) { |
292 Node u = _graph.target(e); |
290 Node u = _graph.target(e); |
293 _flow->set(e, (*_capacity)[e]); |
291 _flow->set(e, (*_capacity)[e]); |
294 _excess->set(u, (*_excess)[u] + (*_capacity)[e]); |
292 _excess->set(u, (*_excess)[u] + (*_capacity)[e]); |
295 if (!(*_active)[u] && u != _source) { |
293 if (!(*_active)[u] && u != _source) { |
296 activate(u); |
294 activate(u); |
297 } |
295 } |
298 } |
296 } |
299 } |
297 } |
|
298 |
300 if ((*_active)[target]) { |
299 if ((*_active)[target]) { |
301 deactivate(target); |
300 deactivate(target); |
302 } |
301 } |
303 |
302 |
304 _highest = _sets.back().begin(); |
303 _highest = _sets.back().begin(); |
305 while (_highest != _sets.back().end() && |
304 while (_highest != _sets.back().end() && |
306 !(*_active)[_first[*_highest]]) { |
305 !(*_active)[_first[*_highest]]) { |
307 ++_highest; |
306 ++_highest; |
308 } |
307 } |
309 } |
308 } |
310 |
|
311 |
309 |
312 while (true) { |
310 while (true) { |
313 while (_highest != _sets.back().end()) { |
311 while (_highest != _sets.back().end()) { |
314 Node n = _first[*_highest]; |
312 Node n = _first[*_highest]; |
315 Value excess = (*_excess)[n]; |
313 Value excess = (*_excess)[n]; |
460 } |
458 } |
461 } |
459 } |
462 |
460 |
463 { |
461 { |
464 Node new_target; |
462 Node new_target; |
465 if ((*_prev)[target] != INVALID) { |
463 if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) { |
466 _last[(*_bucket)[target]] = (*_prev)[target]; |
464 if ((*_next)[target] == INVALID) { |
467 _next->set((*_prev)[target], INVALID); |
465 _last[(*_bucket)[target]] = (*_prev)[target]; |
468 new_target = (*_prev)[target]; |
466 new_target = (*_prev)[target]; |
|
467 } else { |
|
468 _prev->set((*_next)[target], (*_prev)[target]); |
|
469 new_target = (*_next)[target]; |
|
470 } |
|
471 if ((*_prev)[target] == INVALID) { |
|
472 _first[(*_bucket)[target]] = (*_next)[target]; |
|
473 } else { |
|
474 _next->set((*_prev)[target], (*_next)[target]); |
|
475 } |
469 } else { |
476 } else { |
470 _sets.back().pop_back(); |
477 _sets.back().pop_back(); |
471 if (_sets.back().empty()) { |
478 if (_sets.back().empty()) { |
472 _sets.pop_back(); |
479 _sets.pop_back(); |
473 if (_sets.empty()) |
480 if (_sets.empty()) |
759 } |
766 } |
760 } |
767 } |
761 |
768 |
762 { |
769 { |
763 Node new_target; |
770 Node new_target; |
764 if ((*_prev)[target] != INVALID) { |
771 if ((*_prev)[target] != INVALID || (*_next)[target] != INVALID) { |
765 _last[(*_bucket)[target]] = (*_prev)[target]; |
772 if ((*_next)[target] == INVALID) { |
766 _next->set((*_prev)[target], INVALID); |
773 _last[(*_bucket)[target]] = (*_prev)[target]; |
767 new_target = (*_prev)[target]; |
774 new_target = (*_prev)[target]; |
|
775 } else { |
|
776 _prev->set((*_next)[target], (*_prev)[target]); |
|
777 new_target = (*_next)[target]; |
|
778 } |
|
779 if ((*_prev)[target] == INVALID) { |
|
780 _first[(*_bucket)[target]] = (*_next)[target]; |
|
781 } else { |
|
782 _next->set((*_prev)[target], (*_next)[target]); |
|
783 } |
768 } else { |
784 } else { |
769 _sets.back().pop_back(); |
785 _sets.back().pop_back(); |
770 if (_sets.back().empty()) { |
786 if (_sets.back().empty()) { |
771 _sets.pop_back(); |
787 _sets.pop_back(); |
772 if (_sets.empty()) |
788 if (_sets.empty()) |
848 void init(const Node& source) { |
864 void init(const Node& source) { |
849 _source = source; |
865 _source = source; |
850 |
866 |
851 _node_num = countNodes(_graph); |
867 _node_num = countNodes(_graph); |
852 |
868 |
853 _first.resize(_node_num); |
869 _first.resize(_node_num + 1); |
854 _last.resize(_node_num); |
870 _last.resize(_node_num + 1); |
855 |
871 |
856 _dormant.resize(_node_num); |
872 _dormant.resize(_node_num + 1); |
857 |
873 |
858 if (!_flow) { |
874 if (!_flow) { |
859 _flow = new FlowMap(_graph); |
875 _flow = new FlowMap(_graph); |
860 } |
876 } |
861 if (!_next) { |
877 if (!_next) { |