Changeset 628:aa1804409f29 in lemon for lemon/hao_orlin.h

Timestamp:

04/14/09 10:35:38 (15 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Message:

Exploit that the standard maps are reference maps (#190)

File:

• lemon/hao_orlin.h (modified) (44 diffs)

lemon/hao_orlin.h

@@ -162 +162 @@
 
     void activate(const Node& i) {
-      _active->set(i, true);
+      (*_active)[i] = true;
 
       int bucket = (*_bucket)[i];
@@ -168 +168 @@
       if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return;
       //unlace
-      _next->set((*_prev)[i], (*_next)[i]);
+      (*_next)[(*_prev)[i]] = (*_next)[i];
       if ((*_next)[i] != INVALID) {
-        _prev->set((*_next)[i], (*_prev)[i]);
+        (*_prev)[(*_next)[i]] = (*_prev)[i];
       } else {
         _last[bucket] = (*_prev)[i];
       }
       //lace
-      _next->set(i, _first[bucket]);
-      _prev->set(_first[bucket], i);
-      _prev->set(i, INVALID);
+      (*_next)[i] = _first[bucket];
+      (*_prev)[_first[bucket]] = i;
+      (*_prev)[i] = INVALID;
       _first[bucket] = i;
     }
 
     void deactivate(const Node& i) {
-      _active->set(i, false);
+      (*_active)[i] = false;
       int bucket = (*_bucket)[i];
 
@@ -188 +188 @@
 
       //unlace
-      _prev->set((*_next)[i], (*_prev)[i]);
+      (*_prev)[(*_next)[i]] = (*_prev)[i];
       if ((*_prev)[i] != INVALID) {
-        _next->set((*_prev)[i], (*_next)[i]);
+        (*_next)[(*_prev)[i]] = (*_next)[i];
       } else {
         _first[bucket] = (*_next)[i];
       }
       //lace
-      _prev->set(i, _last[bucket]);
-      _next->set(_last[bucket], i);
-      _next->set(i, INVALID);
+      (*_prev)[i] = _last[bucket];
+      (*_next)[_last[bucket]] = i;
+      (*_next)[i] = INVALID;
       _last[bucket] = i;
     }
@@ -204 +204 @@
       (*_bucket)[i] = bucket;
       if (_last[bucket] != INVALID) {
-        _prev->set(i, _last[bucket]);
-        _next->set(_last[bucket], i);
-        _next->set(i, INVALID);
+        (*_prev)[i] = _last[bucket];
+        (*_next)[_last[bucket]] = i;
+        (*_next)[i] = INVALID;
         _last[bucket] = i;
       } else {
-        _prev->set(i, INVALID);
+        (*_prev)[i] = INVALID;
         _first[bucket] = i;
-        _next->set(i, INVALID);
+        (*_next)[i] = INVALID;
         _last[bucket] = i;
       }
@@ -219 +219 @@
 
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        _excess->set(n, 0);
+        (*_excess)[n] = 0;
       }
 
       for (ArcIt a(_graph); a != INVALID; ++a) {
-        _flow->set(a, 0);
+        (*_flow)[a] = 0;
       }
 
@@ -233 +233 @@
         typename Digraph::template NodeMap<bool> reached(_graph, false);
 
-        reached.set(_source, true);
+        reached[_source] = true;
         bool first_set = true;
 
@@ -241 +241 @@
 
           queue[qlast++] = t;
-          reached.set(t, true);
+          reached[t] = true;
 
           while (qfirst != qlast) {
@@ -258 +258 @@
               Node u = _graph.source(a);
               if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
-                reached.set(u, true);
+                reached[u] = true;
                 queue[qlast++] = u;
               }
@@ -267 +267 @@
 
         ++bucket_num;
-        _bucket->set(_source, 0);
+        (*_bucket)[_source] = 0;
         _dormant[0] = true;
       }
-      _source_set->set(_source, true);
+      (*_source_set)[_source] = true;
 
       Node target = _last[_sets.back().back()];
@@ -277 +277 @@
           if (_tolerance.positive((*_capacity)[a])) {
             Node u = _graph.target(a);
-            _flow->set(a, (*_capacity)[a]);
-            _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
+            (*_flow)[a] = (*_capacity)[a];
+            (*_excess)[u] += (*_capacity)[a];
             if (!(*_active)[u] && u != _source) {
               activate(u);
@@ -319 +319 @@
               }
               if (!_tolerance.less(rem, excess)) {
-                _flow->set(a, (*_flow)[a] + excess);
-                _excess->set(v, (*_excess)[v] + excess);
+                (*_flow)[a] += excess;
+                (*_excess)[v] += excess;
                 excess = 0;
                 goto no_more_push;
               } else {
                 excess -= rem;
-                _excess->set(v, (*_excess)[v] + rem);
-                _flow->set(a, (*_capacity)[a]);
+                (*_excess)[v] += rem;
+                (*_flow)[a] = (*_capacity)[a];
               }
             } else if (next_bucket > (*_bucket)[v]) {
@@ -343 +343 @@
               }
               if (!_tolerance.less(rem, excess)) {
-                _flow->set(a, (*_flow)[a] - excess);
-                _excess->set(v, (*_excess)[v] + excess);
+                (*_flow)[a] -= excess;
+                (*_excess)[v] += excess;
                 excess = 0;
                 goto no_more_push;
               } else {
                 excess -= rem;
-                _excess->set(v, (*_excess)[v] + rem);
-                _flow->set(a, 0);
+                (*_excess)[v] += rem;
+                (*_flow)[a] = 0;
               }
             } else if (next_bucket > (*_bucket)[v]) {
@@ -359 +359 @@
         no_more_push:
 
-          _excess->set(n, excess);
+          (*_excess)[n] = excess;
 
           if (excess != 0) {
@@ -377 +377 @@
             } else if (next_bucket == _node_num) {
               _first[(*_bucket)[n]] = (*_next)[n];
-              _prev->set((*_next)[n], INVALID);
+              (*_prev)[(*_next)[n]] = INVALID;
 
               std::list<std::list<int> >::iterator new_set =
@@ -383 +383 @@
 
               new_set->push_front(bucket_num);
-              _bucket->set(n, bucket_num);
+              (*_bucket)[n] = bucket_num;
               _first[bucket_num] = _last[bucket_num] = n;
-              _next->set(n, INVALID);
-              _prev->set(n, INVALID);
+              (*_next)[n] = INVALID;
+              (*_prev)[n] = INVALID;
               _dormant[bucket_num] = true;
               ++bucket_num;
@@ -396 +396 @@
             } else {
               _first[*_highest] = (*_next)[n];
-              _prev->set((*_next)[n], INVALID);
+              (*_prev)[(*_next)[n]] = INVALID;
 
               while (next_bucket != *_highest) {
@@ -410 +410 @@
               --_highest;
 
-              _bucket->set(n, *_highest);
-              _next->set(n, _first[*_highest]);
+              (*_bucket)[n] = *_highest;
+              (*_next)[n] = _first[*_highest];
               if (_first[*_highest] != INVALID) {
-                _prev->set(_first[*_highest], n);
+                (*_prev)[_first[*_highest]] = n;
               } else {
                 _last[*_highest] = n;
@@ -435 +435 @@
           _min_cut = (*_excess)[target];
           for (NodeIt i(_graph); i != INVALID; ++i) {
-            _min_cut_map->set(i, true);
+            (*_min_cut_map)[i] = true;
           }
           for (std::list<int>::iterator it = _sets.back().begin();
@@ -441 +441 @@
             Node n = _first[*it];
             while (n != INVALID) {
-              _min_cut_map->set(n, false);
+              (*_min_cut_map)[n] = false;
               n = (*_next)[n];
             }
@@ -454 +454 @@
               new_target = (*_prev)[target];
             } else {
-              _prev->set((*_next)[target], (*_prev)[target]);
+              (*_prev)[(*_next)[target]] = (*_prev)[target];
               new_target = (*_next)[target];
             }
@@ -460 +460 @@
               _first[(*_bucket)[target]] = (*_next)[target];
             } else {
-              _next->set((*_prev)[target], (*_next)[target]);
+              (*_next)[(*_prev)[target]] = (*_next)[target];
             }
           } else {
@@ -476 +476 @@
           }
 
-          _bucket->set(target, 0);
-
-          _source_set->set(target, true);
+          (*_bucket)[target] = 0;
+
+          (*_source_set)[target] = true;
           for (OutArcIt a(_graph, target); a != INVALID; ++a) {
             Value rem = (*_capacity)[a] - (*_flow)[a];
@@ -486 +486 @@
               activate(v);
             }
-            _excess->set(v, (*_excess)[v] + rem);
-            _flow->set(a, (*_capacity)[a]);
+            (*_excess)[v] += rem;
+            (*_flow)[a] = (*_capacity)[a];
           }
 
@@ -497 +497 @@
               activate(v);
             }
-            _excess->set(v, (*_excess)[v] + rem);
-            _flow->set(a, 0);
+            (*_excess)[v] += rem;
+            (*_flow)[a] = 0;
           }
 
@@ -518 +518 @@
 
       for (NodeIt n(_graph); n != INVALID; ++n) {
-        _excess->set(n, 0);
+        (*_excess)[n] = 0;
       }
 
       for (ArcIt a(_graph); a != INVALID; ++a) {
-        _flow->set(a, 0);
+        (*_flow)[a] = 0;
       }
 
@@ -532 +532 @@
         typename Digraph::template NodeMap<bool> reached(_graph, false);
 
-        reached.set(_source, true);
+        reached[_source] = true;
 
         bool first_set = true;
@@ -541 +541 @@
 
           queue[qlast++] = t;
-          reached.set(t, true);
+          reached[t] = true;
 
           while (qfirst != qlast) {
@@ -558 +558 @@
               Node u = _graph.target(a);
               if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
-                reached.set(u, true);
+                reached[u] = true;
                 queue[qlast++] = u;
               }
@@ -567 +567 @@
 
         ++bucket_num;
-        _bucket->set(_source, 0);
+        (*_bucket)[_source] = 0;
         _dormant[0] = true;
       }
-      _source_set->set(_source, true);
+      (*_source_set)[_source] = true;
 
       Node target = _last[_sets.back().back()];
@@ -577 +577 @@
           if (_tolerance.positive((*_capacity)[a])) {
             Node u = _graph.source(a);
-            _flow->set(a, (*_capacity)[a]);
-            _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
+            (*_flow)[a] = (*_capacity)[a];
+            (*_excess)[u] += (*_capacity)[a];
             if (!(*_active)[u] && u != _source) {
               activate(u);
@@ -619 +619 @@
               }
               if (!_tolerance.less(rem, excess)) {
-                _flow->set(a, (*_flow)[a] + excess);
-                _excess->set(v, (*_excess)[v] + excess);
+                (*_flow)[a] += excess;
+                (*_excess)[v] += excess;
                 excess = 0;
                 goto no_more_push;
               } else {
                 excess -= rem;
-                _excess->set(v, (*_excess)[v] + rem);
-                _flow->set(a, (*_capacity)[a]);
+                (*_excess)[v] += rem;
+                (*_flow)[a] = (*_capacity)[a];
               }
             } else if (next_bucket > (*_bucket)[v]) {
@@ -643 +643 @@
               }
               if (!_tolerance.less(rem, excess)) {
-                _flow->set(a, (*_flow)[a] - excess);
-                _excess->set(v, (*_excess)[v] + excess);
+                (*_flow)[a] -= excess;
+                (*_excess)[v] += excess;
                 excess = 0;
                 goto no_more_push;
               } else {
                 excess -= rem;
-                _excess->set(v, (*_excess)[v] + rem);
-                _flow->set(a, 0);
+                (*_excess)[v] += rem;
+                (*_flow)[a] = 0;
               }
             } else if (next_bucket > (*_bucket)[v]) {
@@ -659 +659 @@
         no_more_push:
 
-          _excess->set(n, excess);
+          (*_excess)[n] = excess;
 
           if (excess != 0) {
@@ -677 +677 @@
             } else if (next_bucket == _node_num) {
               _first[(*_bucket)[n]] = (*_next)[n];
-              _prev->set((*_next)[n], INVALID);
+              (*_prev)[(*_next)[n]] = INVALID;
 
               std::list<std::list<int> >::iterator new_set =
@@ -683 +683 @@
 
               new_set->push_front(bucket_num);
-              _bucket->set(n, bucket_num);
+              (*_bucket)[n] = bucket_num;
               _first[bucket_num] = _last[bucket_num] = n;
-              _next->set(n, INVALID);
-              _prev->set(n, INVALID);
+              (*_next)[n] = INVALID;
+              (*_prev)[n] = INVALID;
               _dormant[bucket_num] = true;
               ++bucket_num;
@@ -696 +696 @@
             } else {
               _first[*_highest] = (*_next)[n];
-              _prev->set((*_next)[n], INVALID);
+              (*_prev)[(*_next)[n]] = INVALID;
 
               while (next_bucket != *_highest) {
@@ -709 +709 @@
               --_highest;
 
-              _bucket->set(n, *_highest);
-              _next->set(n, _first[*_highest]);
+              (*_bucket)[n] = *_highest;
+              (*_next)[n] = _first[*_highest];
               if (_first[*_highest] != INVALID) {
-                _prev->set(_first[*_highest], n);
+                (*_prev)[_first[*_highest]] = n;
               } else {
                 _last[*_highest] = n;
@@ -734 +734 @@
           _min_cut = (*_excess)[target];
           for (NodeIt i(_graph); i != INVALID; ++i) {
-            _min_cut_map->set(i, false);
+            (*_min_cut_map)[i] = false;
           }
           for (std::list<int>::iterator it = _sets.back().begin();
@@ -740 +740 @@
             Node n = _first[*it];
             while (n != INVALID) {
-              _min_cut_map->set(n, true);
+              (*_min_cut_map)[n] = true;
               n = (*_next)[n];
             }
@@ -753 +753 @@
               new_target = (*_prev)[target];
             } else {
-              _prev->set((*_next)[target], (*_prev)[target]);
+              (*_prev)[(*_next)[target]] = (*_prev)[target];
               new_target = (*_next)[target];
             }
@@ -759 +759 @@
               _first[(*_bucket)[target]] = (*_next)[target];
             } else {
-              _next->set((*_prev)[target], (*_next)[target]);
+              (*_next)[(*_prev)[target]] = (*_next)[target];
             }
           } else {
@@ -775 +775 @@
           }
 
-          _bucket->set(target, 0);
-
-          _source_set->set(target, true);
+          (*_bucket)[target] = 0;
+
+          (*_source_set)[target] = true;
           for (InArcIt a(_graph, target); a != INVALID; ++a) {
             Value rem = (*_capacity)[a] - (*_flow)[a];
@@ -785 +785 @@
               activate(v);
             }
-            _excess->set(v, (*_excess)[v] + rem);
-            _flow->set(a, (*_capacity)[a]);
+            (*_excess)[v] += rem;
+            (*_flow)[a] = (*_capacity)[a];
           }
 
@@ -796 +796 @@
               activate(v);
             }
-            _excess->set(v, (*_excess)[v] + rem);
-            _flow->set(a, 0);
+            (*_excess)[v] += rem;
+            (*_flow)[a] = 0;
           }