1.1 --- a/lemon/hao_orlin.h Thu Jan 11 21:20:57 2007 +0000
1.2 +++ b/lemon/hao_orlin.h Thu Jan 11 21:22:39 2007 +0000
1.3 @@ -19,15 +19,19 @@
1.4 #ifndef LEMON_HAO_ORLIN_H
1.5 #define LEMON_HAO_ORLIN_H
1.6
1.7 +#include <cassert>
1.8 +
1.9 +
1.10 +
1.11 #include <vector>
1.12 #include <queue>
1.13 +#include <list>
1.14 #include <limits>
1.15
1.16 #include <lemon/maps.h>
1.17 #include <lemon/graph_utils.h>
1.18 #include <lemon/graph_adaptor.h>
1.19 #include <lemon/iterable_maps.h>
1.20 -
1.21
1.22 /// \file
1.23 /// \ingroup flowalgs
1.24 @@ -108,9 +112,6 @@
1.25
1.26 OutResGraph* _out_res_graph;
1.27
1.28 - typedef typename Graph::template NodeMap<OutResEdge> OutCurrentEdgeMap;
1.29 - OutCurrentEdgeMap* _out_current_edge;
1.30 -
1.31 typedef RevGraphAdaptor<const Graph> RevGraph;
1.32 RevGraph* _rev_graph;
1.33
1.34 @@ -120,10 +121,6 @@
1.35
1.36 InResGraph* _in_res_graph;
1.37
1.38 - typedef typename Graph::template NodeMap<InResEdge> InCurrentEdgeMap;
1.39 - InCurrentEdgeMap* _in_current_edge;
1.40 -
1.41 -
1.42 typedef IterableBoolMap<Graph, Node> WakeMap;
1.43 WakeMap* _wake;
1.44
1.45 @@ -161,8 +158,7 @@
1.46 const Tolerance& tolerance = Tolerance()) :
1.47 _graph(&graph), _capacity(&capacity),
1.48 _preflow(0), _source(), _target(),
1.49 - _out_res_graph(0), _out_current_edge(0),
1.50 - _rev_graph(0), _in_res_graph(0), _in_current_edge(0),
1.51 + _out_res_graph(0), _rev_graph(0), _in_res_graph(0),
1.52 _wake(0),_dist(0), _excess(0), _source_set(0),
1.53 _highest_active(), _active_nodes(), _dormant_max(), _dormant(),
1.54 _min_cut(), _min_cut_map(0), _tolerance(tolerance) {}
1.55 @@ -171,18 +167,12 @@
1.56 if (_min_cut_map) {
1.57 delete _min_cut_map;
1.58 }
1.59 - if (_in_current_edge) {
1.60 - delete _in_current_edge;
1.61 - }
1.62 if (_in_res_graph) {
1.63 delete _in_res_graph;
1.64 }
1.65 if (_rev_graph) {
1.66 delete _rev_graph;
1.67 }
1.68 - if (_out_current_edge) {
1.69 - delete _out_current_edge;
1.70 - }
1.71 if (_out_res_graph) {
1.72 delete _out_res_graph;
1.73 }
1.74 @@ -205,9 +195,9 @@
1.75
1.76 private:
1.77
1.78 - template <typename ResGraph, typename EdgeMap>
1.79 - void findMinCut(const Node& target, bool out,
1.80 - ResGraph& res_graph, EdgeMap& current_edge) {
1.81 + template <typename ResGraph>
1.82 + void findMinCut(const Node& target, bool out, ResGraph& res_graph) {
1.83 + typedef typename Graph::Node Node;
1.84 typedef typename ResGraph::Edge ResEdge;
1.85 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
1.86
1.87 @@ -219,28 +209,6 @@
1.88 (*_dist)[it] = 1;
1.89 (*_excess)[it] = 0;
1.90 (*_source_set)[it] = false;
1.91 -
1.92 - res_graph.firstOut(current_edge[it], it);
1.93 - }
1.94 -
1.95 - _target = target;
1.96 - (*_dist)[target] = 0;
1.97 -
1.98 - for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) {
1.99 - Value delta = res_graph.rescap(it);
1.100 - if (!_tolerance.positive(delta)) continue;
1.101 -
1.102 - (*_excess)[res_graph.source(it)] -= delta;
1.103 - res_graph.augment(it, delta);
1.104 - Node a = res_graph.target(it);
1.105 - if (!_tolerance.positive((*_excess)[a]) &&
1.106 - (*_wake)[a] && a != _target) {
1.107 - _active_nodes[(*_dist)[a]].push_front(a);
1.108 - if (_highest_active < (*_dist)[a]) {
1.109 - _highest_active = (*_dist)[a];
1.110 - }
1.111 - }
1.112 - (*_excess)[a] += delta;
1.113 }
1.114
1.115 _dormant[0].push_front(_source);
1.116 @@ -251,31 +219,46 @@
1.117 _level_size[0] = 1;
1.118 _level_size[1] = _node_num - 1;
1.119
1.120 + _target = target;
1.121 + (*_dist)[target] = 0;
1.122 +
1.123 + for (ResOutEdgeIt it(res_graph, _source); it != INVALID; ++it) {
1.124 + Value delta = res_graph.rescap(it);
1.125 + (*_excess)[_source] -= delta;
1.126 + res_graph.augment(it, delta);
1.127 + Node a = res_graph.target(it);
1.128 + if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
1.129 + _active_nodes[(*_dist)[a]].push_front(a);
1.130 + if (_highest_active < (*_dist)[a]) {
1.131 + _highest_active = (*_dist)[a];
1.132 + }
1.133 + }
1.134 + (*_excess)[a] += delta;
1.135 + }
1.136 +
1.137 +
1.138 do {
1.139 Node n;
1.140 while ((n = findActiveNode()) != INVALID) {
1.141 - ResEdge e;
1.142 - while (_tolerance.positive((*_excess)[n]) &&
1.143 - (e = findAdmissibleEdge(n, res_graph, current_edge))
1.144 - != INVALID){
1.145 - Value delta;
1.146 - if ((*_excess)[n] < res_graph.rescap(e)) {
1.147 + for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
1.148 + Node a = res_graph.target(e);
1.149 + if ((*_dist)[a] >= (*_dist)[n] || !(*_wake)[a]) continue;
1.150 + Value delta = res_graph.rescap(e);
1.151 + if (_tolerance.positive((*_excess)[n] - delta)) {
1.152 + (*_excess)[n] -= delta;
1.153 + } else {
1.154 delta = (*_excess)[n];
1.155 - } else {
1.156 - delta = res_graph.rescap(e);
1.157 - res_graph.nextOut(current_edge[n]);
1.158 + (*_excess)[n] = 0;
1.159 }
1.160 - if (!_tolerance.positive(delta)) continue;
1.161 res_graph.augment(e, delta);
1.162 - (*_excess)[res_graph.source(e)] -= delta;
1.163 - Node a = res_graph.target(e);
1.164 - if (!_tolerance.positive((*_excess)[a]) && a != _target) {
1.165 + if ((*_excess)[a] == 0 && a != _target) {
1.166 _active_nodes[(*_dist)[a]].push_front(a);
1.167 }
1.168 (*_excess)[a] += delta;
1.169 + if ((*_excess)[n] == 0) break;
1.170 }
1.171 - if (_tolerance.positive((*_excess)[n])) {
1.172 - relabel(n, res_graph, current_edge);
1.173 + if ((*_excess)[n] != 0) {
1.174 + relabel(n, res_graph);
1.175 }
1.176 }
1.177
1.178 @@ -297,8 +280,8 @@
1.179 } while (selectNewSink(res_graph));
1.180 }
1.181
1.182 - template <typename ResGraph, typename EdgeMap>
1.183 - void relabel(const Node& n, ResGraph& res_graph, EdgeMap& current_edge) {
1.184 + template <typename ResGraph>
1.185 + void relabel(const Node& n, ResGraph& res_graph) {
1.186 typedef typename ResGraph::OutEdgeIt ResOutEdgeIt;
1.187
1.188 int k = (*_dist)[n];
1.189 @@ -311,7 +294,7 @@
1.190 --_level_size[(*_dist)[it]];
1.191 }
1.192 }
1.193 - --_highest_active;
1.194 + --_highest_active;
1.195 } else {
1.196 int new_dist = _node_num;
1.197 for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e) {
1.198 @@ -331,7 +314,6 @@
1.199 _highest_active = (*_dist)[n];
1.200 _active_nodes[_highest_active].push_front(n);
1.201 ++_level_size[(*_dist)[n]];
1.202 - res_graph.firstOut(current_edge[n], n);
1.203 }
1.204 }
1.205 }
1.206 @@ -372,38 +354,34 @@
1.207
1.208 if (wake_was_empty){
1.209 for (typename WakeMap::TrueIt it(*_wake); it != INVALID; ++it) {
1.210 - if (_tolerance.positive((*_excess)[it])) {
1.211 - if ((*_wake)[it] && it != _target) {
1.212 - _active_nodes[(*_dist)[it]].push_front(it);
1.213 - }
1.214 - if (_highest_active < (*_dist)[it]) {
1.215 - _highest_active = (*_dist)[it];
1.216 + if ((*_excess)[it] != 0 && it != _target) {
1.217 + _active_nodes[(*_dist)[it]].push_front(it);
1.218 + if (_highest_active < (*_dist)[it]) {
1.219 + _highest_active = (*_dist)[it];
1.220 }
1.221 }
1.222 }
1.223 }
1.224
1.225 - for (ResOutEdgeIt e(res_graph, old_target); e!=INVALID; ++e){
1.226 - if (!(*_source_set)[res_graph.target(e)]) {
1.227 - Value delta = res_graph.rescap(e);
1.228 - if (!_tolerance.positive(delta)) continue;
1.229 - res_graph.augment(e, delta);
1.230 - (*_excess)[res_graph.source(e)] -= delta;
1.231 - Node a = res_graph.target(e);
1.232 - if (!_tolerance.positive((*_excess)[a]) &&
1.233 - (*_wake)[a] && a != _target) {
1.234 - _active_nodes[(*_dist)[a]].push_front(a);
1.235 - if (_highest_active < (*_dist)[a]) {
1.236 - _highest_active = (*_dist)[a];
1.237 - }
1.238 + Node n = old_target;
1.239 + for (ResOutEdgeIt e(res_graph, n); e != INVALID; ++e){
1.240 + Node a = res_graph.target(e);
1.241 + if (!(*_wake)[a]) continue;
1.242 + Value delta = res_graph.rescap(e);
1.243 + res_graph.augment(e, delta);
1.244 + (*_excess)[n] -= delta;
1.245 + if ((*_excess)[a] == 0 && (*_wake)[a] && a != _target) {
1.246 + _active_nodes[(*_dist)[a]].push_front(a);
1.247 + if (_highest_active < (*_dist)[a]) {
1.248 + _highest_active = (*_dist)[a];
1.249 }
1.250 - (*_excess)[a] += delta;
1.251 - }
1.252 + }
1.253 + (*_excess)[a] += delta;
1.254 }
1.255
1.256 return true;
1.257 }
1.258 -
1.259 +
1.260 Node findActiveNode() {
1.261 while (_highest_active > 0 && _active_nodes[_highest_active].empty()){
1.262 --_highest_active;
1.263 @@ -417,25 +395,6 @@
1.264 }
1.265 }
1.266
1.267 - template <typename ResGraph, typename EdgeMap>
1.268 - typename ResGraph::Edge findAdmissibleEdge(const Node& n,
1.269 - ResGraph& res_graph,
1.270 - EdgeMap& current_edge) {
1.271 - typedef typename ResGraph::Edge ResEdge;
1.272 - ResEdge e = current_edge[n];
1.273 - while (e != INVALID &&
1.274 - ((*_dist)[n] <= (*_dist)[res_graph.target(e)] ||
1.275 - !(*_wake)[res_graph.target(e)])) {
1.276 - res_graph.nextOut(e);
1.277 - }
1.278 - if (e != INVALID) {
1.279 - current_edge[n] = e;
1.280 - return e;
1.281 - } else {
1.282 - return INVALID;
1.283 - }
1.284 - }
1.285 -
1.286 Value cutValue(bool out) {
1.287 Value value = 0;
1.288 if (out) {
1.289 @@ -512,18 +471,12 @@
1.290 if (!_out_res_graph) {
1.291 _out_res_graph = new OutResGraph(*_graph, *_capacity, *_preflow);
1.292 }
1.293 - if (!_out_current_edge) {
1.294 - _out_current_edge = new OutCurrentEdgeMap(*_graph);
1.295 - }
1.296 if (!_rev_graph) {
1.297 _rev_graph = new RevGraph(*_graph);
1.298 }
1.299 if (!_in_res_graph) {
1.300 _in_res_graph = new InResGraph(*_rev_graph, *_capacity, *_preflow);
1.301 }
1.302 - if (!_in_current_edge) {
1.303 - _in_current_edge = new InCurrentEdgeMap(*_graph);
1.304 - }
1.305 if (!_min_cut_map) {
1.306 _min_cut_map = new MinCutMap(*_graph);
1.307 }
1.308 @@ -555,7 +508,7 @@
1.309 /// and minimal out-degree). The \c target is the initial target
1.310 /// for the push-relabel algorithm.
1.311 void calculateOut(const Node& target) {
1.312 - findMinCut(target, true, *_out_res_graph, *_out_current_edge);
1.313 + findMinCut(target, true, *_out_res_graph);
1.314 }
1.315
1.316 /// \brief Calculates a minimum cut with \f$ source \f$ on the
1.317 @@ -583,7 +536,7 @@
1.318 /// The \c target is the initial
1.319 /// target for the push-relabel algorithm.
1.320 void calculateIn(const Node& target) {
1.321 - findMinCut(target, false, *_in_res_graph, *_in_current_edge);
1.322 + findMinCut(target, false, *_in_res_graph);
1.323 }
1.324
1.325 /// \brief Runs the algorithm.