1.1 --- a/lemon/hao_orlin.h Tue Apr 14 10:34:12 2009 +0200
1.2 +++ b/lemon/hao_orlin.h Tue Apr 14 10:35:38 2009 +0200
1.3 @@ -161,56 +161,56 @@
1.4 private:
1.5
1.6 void activate(const Node& i) {
1.7 - _active->set(i, true);
1.8 + (*_active)[i] = true;
1.9
1.10 int bucket = (*_bucket)[i];
1.11
1.12 if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return;
1.13 //unlace
1.14 - _next->set((*_prev)[i], (*_next)[i]);
1.15 + (*_next)[(*_prev)[i]] = (*_next)[i];
1.16 if ((*_next)[i] != INVALID) {
1.17 - _prev->set((*_next)[i], (*_prev)[i]);
1.18 + (*_prev)[(*_next)[i]] = (*_prev)[i];
1.19 } else {
1.20 _last[bucket] = (*_prev)[i];
1.21 }
1.22 //lace
1.23 - _next->set(i, _first[bucket]);
1.24 - _prev->set(_first[bucket], i);
1.25 - _prev->set(i, INVALID);
1.26 + (*_next)[i] = _first[bucket];
1.27 + (*_prev)[_first[bucket]] = i;
1.28 + (*_prev)[i] = INVALID;
1.29 _first[bucket] = i;
1.30 }
1.31
1.32 void deactivate(const Node& i) {
1.33 - _active->set(i, false);
1.34 + (*_active)[i] = false;
1.35 int bucket = (*_bucket)[i];
1.36
1.37 if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return;
1.38
1.39 //unlace
1.40 - _prev->set((*_next)[i], (*_prev)[i]);
1.41 + (*_prev)[(*_next)[i]] = (*_prev)[i];
1.42 if ((*_prev)[i] != INVALID) {
1.43 - _next->set((*_prev)[i], (*_next)[i]);
1.44 + (*_next)[(*_prev)[i]] = (*_next)[i];
1.45 } else {
1.46 _first[bucket] = (*_next)[i];
1.47 }
1.48 //lace
1.49 - _prev->set(i, _last[bucket]);
1.50 - _next->set(_last[bucket], i);
1.51 - _next->set(i, INVALID);
1.52 + (*_prev)[i] = _last[bucket];
1.53 + (*_next)[_last[bucket]] = i;
1.54 + (*_next)[i] = INVALID;
1.55 _last[bucket] = i;
1.56 }
1.57
1.58 void addItem(const Node& i, int bucket) {
1.59 (*_bucket)[i] = bucket;
1.60 if (_last[bucket] != INVALID) {
1.61 - _prev->set(i, _last[bucket]);
1.62 - _next->set(_last[bucket], i);
1.63 - _next->set(i, INVALID);
1.64 + (*_prev)[i] = _last[bucket];
1.65 + (*_next)[_last[bucket]] = i;
1.66 + (*_next)[i] = INVALID;
1.67 _last[bucket] = i;
1.68 } else {
1.69 - _prev->set(i, INVALID);
1.70 + (*_prev)[i] = INVALID;
1.71 _first[bucket] = i;
1.72 - _next->set(i, INVALID);
1.73 + (*_next)[i] = INVALID;
1.74 _last[bucket] = i;
1.75 }
1.76 }
1.77 @@ -218,11 +218,11 @@
1.78 void findMinCutOut() {
1.79
1.80 for (NodeIt n(_graph); n != INVALID; ++n) {
1.81 - _excess->set(n, 0);
1.82 + (*_excess)[n] = 0;
1.83 }
1.84
1.85 for (ArcIt a(_graph); a != INVALID; ++a) {
1.86 - _flow->set(a, 0);
1.87 + (*_flow)[a] = 0;
1.88 }
1.89
1.90 int bucket_num = 0;
1.91 @@ -232,7 +232,7 @@
1.92 {
1.93 typename Digraph::template NodeMap<bool> reached(_graph, false);
1.94
1.95 - reached.set(_source, true);
1.96 + reached[_source] = true;
1.97 bool first_set = true;
1.98
1.99 for (NodeIt t(_graph); t != INVALID; ++t) {
1.100 @@ -240,7 +240,7 @@
1.101 _sets.push_front(std::list<int>());
1.102
1.103 queue[qlast++] = t;
1.104 - reached.set(t, true);
1.105 + reached[t] = true;
1.106
1.107 while (qfirst != qlast) {
1.108 if (qsep == qfirst) {
1.109 @@ -257,7 +257,7 @@
1.110 for (InArcIt a(_graph, n); a != INVALID; ++a) {
1.111 Node u = _graph.source(a);
1.112 if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
1.113 - reached.set(u, true);
1.114 + reached[u] = true;
1.115 queue[qlast++] = u;
1.116 }
1.117 }
1.118 @@ -266,18 +266,18 @@
1.119 }
1.120
1.121 ++bucket_num;
1.122 - _bucket->set(_source, 0);
1.123 + (*_bucket)[_source] = 0;
1.124 _dormant[0] = true;
1.125 }
1.126 - _source_set->set(_source, true);
1.127 + (*_source_set)[_source] = true;
1.128
1.129 Node target = _last[_sets.back().back()];
1.130 {
1.131 for (OutArcIt a(_graph, _source); a != INVALID; ++a) {
1.132 if (_tolerance.positive((*_capacity)[a])) {
1.133 Node u = _graph.target(a);
1.134 - _flow->set(a, (*_capacity)[a]);
1.135 - _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
1.136 + (*_flow)[a] = (*_capacity)[a];
1.137 + (*_excess)[u] += (*_capacity)[a];
1.138 if (!(*_active)[u] && u != _source) {
1.139 activate(u);
1.140 }
1.141 @@ -318,14 +318,14 @@
1.142 activate(v);
1.143 }
1.144 if (!_tolerance.less(rem, excess)) {
1.145 - _flow->set(a, (*_flow)[a] + excess);
1.146 - _excess->set(v, (*_excess)[v] + excess);
1.147 + (*_flow)[a] += excess;
1.148 + (*_excess)[v] += excess;
1.149 excess = 0;
1.150 goto no_more_push;
1.151 } else {
1.152 excess -= rem;
1.153 - _excess->set(v, (*_excess)[v] + rem);
1.154 - _flow->set(a, (*_capacity)[a]);
1.155 + (*_excess)[v] += rem;
1.156 + (*_flow)[a] = (*_capacity)[a];
1.157 }
1.158 } else if (next_bucket > (*_bucket)[v]) {
1.159 next_bucket = (*_bucket)[v];
1.160 @@ -342,14 +342,14 @@
1.161 activate(v);
1.162 }
1.163 if (!_tolerance.less(rem, excess)) {
1.164 - _flow->set(a, (*_flow)[a] - excess);
1.165 - _excess->set(v, (*_excess)[v] + excess);
1.166 + (*_flow)[a] -= excess;
1.167 + (*_excess)[v] += excess;
1.168 excess = 0;
1.169 goto no_more_push;
1.170 } else {
1.171 excess -= rem;
1.172 - _excess->set(v, (*_excess)[v] + rem);
1.173 - _flow->set(a, 0);
1.174 + (*_excess)[v] += rem;
1.175 + (*_flow)[a] = 0;
1.176 }
1.177 } else if (next_bucket > (*_bucket)[v]) {
1.178 next_bucket = (*_bucket)[v];
1.179 @@ -358,7 +358,7 @@
1.180
1.181 no_more_push:
1.182
1.183 - _excess->set(n, excess);
1.184 + (*_excess)[n] = excess;
1.185
1.186 if (excess != 0) {
1.187 if ((*_next)[n] == INVALID) {
1.188 @@ -376,16 +376,16 @@
1.189 }
1.190 } else if (next_bucket == _node_num) {
1.191 _first[(*_bucket)[n]] = (*_next)[n];
1.192 - _prev->set((*_next)[n], INVALID);
1.193 + (*_prev)[(*_next)[n]] = INVALID;
1.194
1.195 std::list<std::list<int> >::iterator new_set =
1.196 _sets.insert(--_sets.end(), std::list<int>());
1.197
1.198 new_set->push_front(bucket_num);
1.199 - _bucket->set(n, bucket_num);
1.200 + (*_bucket)[n] = bucket_num;
1.201 _first[bucket_num] = _last[bucket_num] = n;
1.202 - _next->set(n, INVALID);
1.203 - _prev->set(n, INVALID);
1.204 + (*_next)[n] = INVALID;
1.205 + (*_prev)[n] = INVALID;
1.206 _dormant[bucket_num] = true;
1.207 ++bucket_num;
1.208
1.209 @@ -395,7 +395,7 @@
1.210 }
1.211 } else {
1.212 _first[*_highest] = (*_next)[n];
1.213 - _prev->set((*_next)[n], INVALID);
1.214 + (*_prev)[(*_next)[n]] = INVALID;
1.215
1.216 while (next_bucket != *_highest) {
1.217 --_highest;
1.218 @@ -409,10 +409,10 @@
1.219 }
1.220 --_highest;
1.221
1.222 - _bucket->set(n, *_highest);
1.223 - _next->set(n, _first[*_highest]);
1.224 + (*_bucket)[n] = *_highest;
1.225 + (*_next)[n] = _first[*_highest];
1.226 if (_first[*_highest] != INVALID) {
1.227 - _prev->set(_first[*_highest], n);
1.228 + (*_prev)[_first[*_highest]] = n;
1.229 } else {
1.230 _last[*_highest] = n;
1.231 }
1.232 @@ -434,13 +434,13 @@
1.233 if ((*_excess)[target] < _min_cut) {
1.234 _min_cut = (*_excess)[target];
1.235 for (NodeIt i(_graph); i != INVALID; ++i) {
1.236 - _min_cut_map->set(i, true);
1.237 + (*_min_cut_map)[i] = true;
1.238 }
1.239 for (std::list<int>::iterator it = _sets.back().begin();
1.240 it != _sets.back().end(); ++it) {
1.241 Node n = _first[*it];
1.242 while (n != INVALID) {
1.243 - _min_cut_map->set(n, false);
1.244 + (*_min_cut_map)[n] = false;
1.245 n = (*_next)[n];
1.246 }
1.247 }
1.248 @@ -453,13 +453,13 @@
1.249 _last[(*_bucket)[target]] = (*_prev)[target];
1.250 new_target = (*_prev)[target];
1.251 } else {
1.252 - _prev->set((*_next)[target], (*_prev)[target]);
1.253 + (*_prev)[(*_next)[target]] = (*_prev)[target];
1.254 new_target = (*_next)[target];
1.255 }
1.256 if ((*_prev)[target] == INVALID) {
1.257 _first[(*_bucket)[target]] = (*_next)[target];
1.258 } else {
1.259 - _next->set((*_prev)[target], (*_next)[target]);
1.260 + (*_next)[(*_prev)[target]] = (*_next)[target];
1.261 }
1.262 } else {
1.263 _sets.back().pop_back();
1.264 @@ -475,9 +475,9 @@
1.265 new_target = _last[_sets.back().back()];
1.266 }
1.267
1.268 - _bucket->set(target, 0);
1.269 + (*_bucket)[target] = 0;
1.270
1.271 - _source_set->set(target, true);
1.272 + (*_source_set)[target] = true;
1.273 for (OutArcIt a(_graph, target); a != INVALID; ++a) {
1.274 Value rem = (*_capacity)[a] - (*_flow)[a];
1.275 if (!_tolerance.positive(rem)) continue;
1.276 @@ -485,8 +485,8 @@
1.277 if (!(*_active)[v] && !(*_source_set)[v]) {
1.278 activate(v);
1.279 }
1.280 - _excess->set(v, (*_excess)[v] + rem);
1.281 - _flow->set(a, (*_capacity)[a]);
1.282 + (*_excess)[v] += rem;
1.283 + (*_flow)[a] = (*_capacity)[a];
1.284 }
1.285
1.286 for (InArcIt a(_graph, target); a != INVALID; ++a) {
1.287 @@ -496,8 +496,8 @@
1.288 if (!(*_active)[v] && !(*_source_set)[v]) {
1.289 activate(v);
1.290 }
1.291 - _excess->set(v, (*_excess)[v] + rem);
1.292 - _flow->set(a, 0);
1.293 + (*_excess)[v] += rem;
1.294 + (*_flow)[a] = 0;
1.295 }
1.296
1.297 target = new_target;
1.298 @@ -517,11 +517,11 @@
1.299 void findMinCutIn() {
1.300
1.301 for (NodeIt n(_graph); n != INVALID; ++n) {
1.302 - _excess->set(n, 0);
1.303 + (*_excess)[n] = 0;
1.304 }
1.305
1.306 for (ArcIt a(_graph); a != INVALID; ++a) {
1.307 - _flow->set(a, 0);
1.308 + (*_flow)[a] = 0;
1.309 }
1.310
1.311 int bucket_num = 0;
1.312 @@ -531,7 +531,7 @@
1.313 {
1.314 typename Digraph::template NodeMap<bool> reached(_graph, false);
1.315
1.316 - reached.set(_source, true);
1.317 + reached[_source] = true;
1.318
1.319 bool first_set = true;
1.320
1.321 @@ -540,7 +540,7 @@
1.322 _sets.push_front(std::list<int>());
1.323
1.324 queue[qlast++] = t;
1.325 - reached.set(t, true);
1.326 + reached[t] = true;
1.327
1.328 while (qfirst != qlast) {
1.329 if (qsep == qfirst) {
1.330 @@ -557,7 +557,7 @@
1.331 for (OutArcIt a(_graph, n); a != INVALID; ++a) {
1.332 Node u = _graph.target(a);
1.333 if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
1.334 - reached.set(u, true);
1.335 + reached[u] = true;
1.336 queue[qlast++] = u;
1.337 }
1.338 }
1.339 @@ -566,18 +566,18 @@
1.340 }
1.341
1.342 ++bucket_num;
1.343 - _bucket->set(_source, 0);
1.344 + (*_bucket)[_source] = 0;
1.345 _dormant[0] = true;
1.346 }
1.347 - _source_set->set(_source, true);
1.348 + (*_source_set)[_source] = true;
1.349
1.350 Node target = _last[_sets.back().back()];
1.351 {
1.352 for (InArcIt a(_graph, _source); a != INVALID; ++a) {
1.353 if (_tolerance.positive((*_capacity)[a])) {
1.354 Node u = _graph.source(a);
1.355 - _flow->set(a, (*_capacity)[a]);
1.356 - _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
1.357 + (*_flow)[a] = (*_capacity)[a];
1.358 + (*_excess)[u] += (*_capacity)[a];
1.359 if (!(*_active)[u] && u != _source) {
1.360 activate(u);
1.361 }
1.362 @@ -618,14 +618,14 @@
1.363 activate(v);
1.364 }
1.365 if (!_tolerance.less(rem, excess)) {
1.366 - _flow->set(a, (*_flow)[a] + excess);
1.367 - _excess->set(v, (*_excess)[v] + excess);
1.368 + (*_flow)[a] += excess;
1.369 + (*_excess)[v] += excess;
1.370 excess = 0;
1.371 goto no_more_push;
1.372 } else {
1.373 excess -= rem;
1.374 - _excess->set(v, (*_excess)[v] + rem);
1.375 - _flow->set(a, (*_capacity)[a]);
1.376 + (*_excess)[v] += rem;
1.377 + (*_flow)[a] = (*_capacity)[a];
1.378 }
1.379 } else if (next_bucket > (*_bucket)[v]) {
1.380 next_bucket = (*_bucket)[v];
1.381 @@ -642,14 +642,14 @@
1.382 activate(v);
1.383 }
1.384 if (!_tolerance.less(rem, excess)) {
1.385 - _flow->set(a, (*_flow)[a] - excess);
1.386 - _excess->set(v, (*_excess)[v] + excess);
1.387 + (*_flow)[a] -= excess;
1.388 + (*_excess)[v] += excess;
1.389 excess = 0;
1.390 goto no_more_push;
1.391 } else {
1.392 excess -= rem;
1.393 - _excess->set(v, (*_excess)[v] + rem);
1.394 - _flow->set(a, 0);
1.395 + (*_excess)[v] += rem;
1.396 + (*_flow)[a] = 0;
1.397 }
1.398 } else if (next_bucket > (*_bucket)[v]) {
1.399 next_bucket = (*_bucket)[v];
1.400 @@ -658,7 +658,7 @@
1.401
1.402 no_more_push:
1.403
1.404 - _excess->set(n, excess);
1.405 + (*_excess)[n] = excess;
1.406
1.407 if (excess != 0) {
1.408 if ((*_next)[n] == INVALID) {
1.409 @@ -676,16 +676,16 @@
1.410 }
1.411 } else if (next_bucket == _node_num) {
1.412 _first[(*_bucket)[n]] = (*_next)[n];
1.413 - _prev->set((*_next)[n], INVALID);
1.414 + (*_prev)[(*_next)[n]] = INVALID;
1.415
1.416 std::list<std::list<int> >::iterator new_set =
1.417 _sets.insert(--_sets.end(), std::list<int>());
1.418
1.419 new_set->push_front(bucket_num);
1.420 - _bucket->set(n, bucket_num);
1.421 + (*_bucket)[n] = bucket_num;
1.422 _first[bucket_num] = _last[bucket_num] = n;
1.423 - _next->set(n, INVALID);
1.424 - _prev->set(n, INVALID);
1.425 + (*_next)[n] = INVALID;
1.426 + (*_prev)[n] = INVALID;
1.427 _dormant[bucket_num] = true;
1.428 ++bucket_num;
1.429
1.430 @@ -695,7 +695,7 @@
1.431 }
1.432 } else {
1.433 _first[*_highest] = (*_next)[n];
1.434 - _prev->set((*_next)[n], INVALID);
1.435 + (*_prev)[(*_next)[n]] = INVALID;
1.436
1.437 while (next_bucket != *_highest) {
1.438 --_highest;
1.439 @@ -708,10 +708,10 @@
1.440 }
1.441 --_highest;
1.442
1.443 - _bucket->set(n, *_highest);
1.444 - _next->set(n, _first[*_highest]);
1.445 + (*_bucket)[n] = *_highest;
1.446 + (*_next)[n] = _first[*_highest];
1.447 if (_first[*_highest] != INVALID) {
1.448 - _prev->set(_first[*_highest], n);
1.449 + (*_prev)[_first[*_highest]] = n;
1.450 } else {
1.451 _last[*_highest] = n;
1.452 }
1.453 @@ -733,13 +733,13 @@
1.454 if ((*_excess)[target] < _min_cut) {
1.455 _min_cut = (*_excess)[target];
1.456 for (NodeIt i(_graph); i != INVALID; ++i) {
1.457 - _min_cut_map->set(i, false);
1.458 + (*_min_cut_map)[i] = false;
1.459 }
1.460 for (std::list<int>::iterator it = _sets.back().begin();
1.461 it != _sets.back().end(); ++it) {
1.462 Node n = _first[*it];
1.463 while (n != INVALID) {
1.464 - _min_cut_map->set(n, true);
1.465 + (*_min_cut_map)[n] = true;
1.466 n = (*_next)[n];
1.467 }
1.468 }
1.469 @@ -752,13 +752,13 @@
1.470 _last[(*_bucket)[target]] = (*_prev)[target];
1.471 new_target = (*_prev)[target];
1.472 } else {
1.473 - _prev->set((*_next)[target], (*_prev)[target]);
1.474 + (*_prev)[(*_next)[target]] = (*_prev)[target];
1.475 new_target = (*_next)[target];
1.476 }
1.477 if ((*_prev)[target] == INVALID) {
1.478 _first[(*_bucket)[target]] = (*_next)[target];
1.479 } else {
1.480 - _next->set((*_prev)[target], (*_next)[target]);
1.481 + (*_next)[(*_prev)[target]] = (*_next)[target];
1.482 }
1.483 } else {
1.484 _sets.back().pop_back();
1.485 @@ -774,9 +774,9 @@
1.486 new_target = _last[_sets.back().back()];
1.487 }
1.488
1.489 - _bucket->set(target, 0);
1.490 + (*_bucket)[target] = 0;
1.491
1.492 - _source_set->set(target, true);
1.493 + (*_source_set)[target] = true;
1.494 for (InArcIt a(_graph, target); a != INVALID; ++a) {
1.495 Value rem = (*_capacity)[a] - (*_flow)[a];
1.496 if (!_tolerance.positive(rem)) continue;
1.497 @@ -784,8 +784,8 @@
1.498 if (!(*_active)[v] && !(*_source_set)[v]) {
1.499 activate(v);
1.500 }
1.501 - _excess->set(v, (*_excess)[v] + rem);
1.502 - _flow->set(a, (*_capacity)[a]);
1.503 + (*_excess)[v] += rem;
1.504 + (*_flow)[a] = (*_capacity)[a];
1.505 }
1.506
1.507 for (OutArcIt a(_graph, target); a != INVALID; ++a) {
1.508 @@ -795,8 +795,8 @@
1.509 if (!(*_active)[v] && !(*_source_set)[v]) {
1.510 activate(v);
1.511 }
1.512 - _excess->set(v, (*_excess)[v] + rem);
1.513 - _flow->set(a, 0);
1.514 + (*_excess)[v] += rem;
1.515 + (*_flow)[a] = 0;
1.516 }
1.517
1.518 target = new_target;