COIN-OR::LEMON - Graph Library

Changeset 581:aa1804409f29 in lemon-1.2 for lemon/hao_orlin.h


Ignore:
Timestamp:
04/14/09 10:35:38 (11 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/hao_orlin.h

    r559 r581  
    162162
    163163    void activate(const Node& i) {
    164       _active->set(i, true);
     164      (*_active)[i] = true;
    165165
    166166      int bucket = (*_bucket)[i];
     
    168168      if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return;
    169169      //unlace
    170       _next->set((*_prev)[i], (*_next)[i]);
     170      (*_next)[(*_prev)[i]] = (*_next)[i];
    171171      if ((*_next)[i] != INVALID) {
    172         _prev->set((*_next)[i], (*_prev)[i]);
     172        (*_prev)[(*_next)[i]] = (*_prev)[i];
    173173      } else {
    174174        _last[bucket] = (*_prev)[i];
    175175      }
    176176      //lace
    177       _next->set(i, _first[bucket]);
    178       _prev->set(_first[bucket], i);
    179       _prev->set(i, INVALID);
     177      (*_next)[i] = _first[bucket];
     178      (*_prev)[_first[bucket]] = i;
     179      (*_prev)[i] = INVALID;
    180180      _first[bucket] = i;
    181181    }
    182182
    183183    void deactivate(const Node& i) {
    184       _active->set(i, false);
     184      (*_active)[i] = false;
    185185      int bucket = (*_bucket)[i];
    186186
     
    188188
    189189      //unlace
    190       _prev->set((*_next)[i], (*_prev)[i]);
     190      (*_prev)[(*_next)[i]] = (*_prev)[i];
    191191      if ((*_prev)[i] != INVALID) {
    192         _next->set((*_prev)[i], (*_next)[i]);
     192        (*_next)[(*_prev)[i]] = (*_next)[i];
    193193      } else {
    194194        _first[bucket] = (*_next)[i];
    195195      }
    196196      //lace
    197       _prev->set(i, _last[bucket]);
    198       _next->set(_last[bucket], i);
    199       _next->set(i, INVALID);
     197      (*_prev)[i] = _last[bucket];
     198      (*_next)[_last[bucket]] = i;
     199      (*_next)[i] = INVALID;
    200200      _last[bucket] = i;
    201201    }
     
    204204      (*_bucket)[i] = bucket;
    205205      if (_last[bucket] != INVALID) {
    206         _prev->set(i, _last[bucket]);
    207         _next->set(_last[bucket], i);
    208         _next->set(i, INVALID);
     206        (*_prev)[i] = _last[bucket];
     207        (*_next)[_last[bucket]] = i;
     208        (*_next)[i] = INVALID;
    209209        _last[bucket] = i;
    210210      } else {
    211         _prev->set(i, INVALID);
     211        (*_prev)[i] = INVALID;
    212212        _first[bucket] = i;
    213         _next->set(i, INVALID);
     213        (*_next)[i] = INVALID;
    214214        _last[bucket] = i;
    215215      }
     
    219219
    220220      for (NodeIt n(_graph); n != INVALID; ++n) {
    221         _excess->set(n, 0);
     221        (*_excess)[n] = 0;
    222222      }
    223223
    224224      for (ArcIt a(_graph); a != INVALID; ++a) {
    225         _flow->set(a, 0);
     225        (*_flow)[a] = 0;
    226226      }
    227227
     
    233233        typename Digraph::template NodeMap<bool> reached(_graph, false);
    234234
    235         reached.set(_source, true);
     235        reached[_source] = true;
    236236        bool first_set = true;
    237237
     
    241241
    242242          queue[qlast++] = t;
    243           reached.set(t, true);
     243          reached[t] = true;
    244244
    245245          while (qfirst != qlast) {
     
    258258              Node u = _graph.source(a);
    259259              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
    260                 reached.set(u, true);
     260                reached[u] = true;
    261261                queue[qlast++] = u;
    262262              }
     
    267267
    268268        ++bucket_num;
    269         _bucket->set(_source, 0);
     269        (*_bucket)[_source] = 0;
    270270        _dormant[0] = true;
    271271      }
    272       _source_set->set(_source, true);
     272      (*_source_set)[_source] = true;
    273273
    274274      Node target = _last[_sets.back().back()];
     
    277277          if (_tolerance.positive((*_capacity)[a])) {
    278278            Node u = _graph.target(a);
    279             _flow->set(a, (*_capacity)[a]);
    280             _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
     279            (*_flow)[a] = (*_capacity)[a];
     280            (*_excess)[u] += (*_capacity)[a];
    281281            if (!(*_active)[u] && u != _source) {
    282282              activate(u);
     
    319319              }
    320320              if (!_tolerance.less(rem, excess)) {
    321                 _flow->set(a, (*_flow)[a] + excess);
    322                 _excess->set(v, (*_excess)[v] + excess);
     321                (*_flow)[a] += excess;
     322                (*_excess)[v] += excess;
    323323                excess = 0;
    324324                goto no_more_push;
    325325              } else {
    326326                excess -= rem;
    327                 _excess->set(v, (*_excess)[v] + rem);
    328                 _flow->set(a, (*_capacity)[a]);
     327                (*_excess)[v] += rem;
     328                (*_flow)[a] = (*_capacity)[a];
    329329              }
    330330            } else if (next_bucket > (*_bucket)[v]) {
     
    343343              }
    344344              if (!_tolerance.less(rem, excess)) {
    345                 _flow->set(a, (*_flow)[a] - excess);
    346                 _excess->set(v, (*_excess)[v] + excess);
     345                (*_flow)[a] -= excess;
     346                (*_excess)[v] += excess;
    347347                excess = 0;
    348348                goto no_more_push;
    349349              } else {
    350350                excess -= rem;
    351                 _excess->set(v, (*_excess)[v] + rem);
    352                 _flow->set(a, 0);
     351                (*_excess)[v] += rem;
     352                (*_flow)[a] = 0;
    353353              }
    354354            } else if (next_bucket > (*_bucket)[v]) {
     
    359359        no_more_push:
    360360
    361           _excess->set(n, excess);
     361          (*_excess)[n] = excess;
    362362
    363363          if (excess != 0) {
     
    377377            } else if (next_bucket == _node_num) {
    378378              _first[(*_bucket)[n]] = (*_next)[n];
    379               _prev->set((*_next)[n], INVALID);
     379              (*_prev)[(*_next)[n]] = INVALID;
    380380
    381381              std::list<std::list<int> >::iterator new_set =
     
    383383
    384384              new_set->push_front(bucket_num);
    385               _bucket->set(n, bucket_num);
     385              (*_bucket)[n] = bucket_num;
    386386              _first[bucket_num] = _last[bucket_num] = n;
    387               _next->set(n, INVALID);
    388               _prev->set(n, INVALID);
     387              (*_next)[n] = INVALID;
     388              (*_prev)[n] = INVALID;
    389389              _dormant[bucket_num] = true;
    390390              ++bucket_num;
     
    396396            } else {
    397397              _first[*_highest] = (*_next)[n];
    398               _prev->set((*_next)[n], INVALID);
     398              (*_prev)[(*_next)[n]] = INVALID;
    399399
    400400              while (next_bucket != *_highest) {
     
    410410              --_highest;
    411411
    412               _bucket->set(n, *_highest);
    413               _next->set(n, _first[*_highest]);
     412              (*_bucket)[n] = *_highest;
     413              (*_next)[n] = _first[*_highest];
    414414              if (_first[*_highest] != INVALID) {
    415                 _prev->set(_first[*_highest], n);
     415                (*_prev)[_first[*_highest]] = n;
    416416              } else {
    417417                _last[*_highest] = n;
     
    435435          _min_cut = (*_excess)[target];
    436436          for (NodeIt i(_graph); i != INVALID; ++i) {
    437             _min_cut_map->set(i, true);
     437            (*_min_cut_map)[i] = true;
    438438          }
    439439          for (std::list<int>::iterator it = _sets.back().begin();
     
    441441            Node n = _first[*it];
    442442            while (n != INVALID) {
    443               _min_cut_map->set(n, false);
     443              (*_min_cut_map)[n] = false;
    444444              n = (*_next)[n];
    445445            }
     
    454454              new_target = (*_prev)[target];
    455455            } else {
    456               _prev->set((*_next)[target], (*_prev)[target]);
     456              (*_prev)[(*_next)[target]] = (*_prev)[target];
    457457              new_target = (*_next)[target];
    458458            }
     
    460460              _first[(*_bucket)[target]] = (*_next)[target];
    461461            } else {
    462               _next->set((*_prev)[target], (*_next)[target]);
     462              (*_next)[(*_prev)[target]] = (*_next)[target];
    463463            }
    464464          } else {
     
    476476          }
    477477
    478           _bucket->set(target, 0);
    479 
    480           _source_set->set(target, true);
     478          (*_bucket)[target] = 0;
     479
     480          (*_source_set)[target] = true;
    481481          for (OutArcIt a(_graph, target); a != INVALID; ++a) {
    482482            Value rem = (*_capacity)[a] - (*_flow)[a];
     
    486486              activate(v);
    487487            }
    488             _excess->set(v, (*_excess)[v] + rem);
    489             _flow->set(a, (*_capacity)[a]);
     488            (*_excess)[v] += rem;
     489            (*_flow)[a] = (*_capacity)[a];
    490490          }
    491491
     
    497497              activate(v);
    498498            }
    499             _excess->set(v, (*_excess)[v] + rem);
    500             _flow->set(a, 0);
     499            (*_excess)[v] += rem;
     500            (*_flow)[a] = 0;
    501501          }
    502502
     
    518518
    519519      for (NodeIt n(_graph); n != INVALID; ++n) {
    520         _excess->set(n, 0);
     520        (*_excess)[n] = 0;
    521521      }
    522522
    523523      for (ArcIt a(_graph); a != INVALID; ++a) {
    524         _flow->set(a, 0);
     524        (*_flow)[a] = 0;
    525525      }
    526526
     
    532532        typename Digraph::template NodeMap<bool> reached(_graph, false);
    533533
    534         reached.set(_source, true);
     534        reached[_source] = true;
    535535
    536536        bool first_set = true;
     
    541541
    542542          queue[qlast++] = t;
    543           reached.set(t, true);
     543          reached[t] = true;
    544544
    545545          while (qfirst != qlast) {
     
    558558              Node u = _graph.target(a);
    559559              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
    560                 reached.set(u, true);
     560                reached[u] = true;
    561561                queue[qlast++] = u;
    562562              }
     
    567567
    568568        ++bucket_num;
    569         _bucket->set(_source, 0);
     569        (*_bucket)[_source] = 0;
    570570        _dormant[0] = true;
    571571      }
    572       _source_set->set(_source, true);
     572      (*_source_set)[_source] = true;
    573573
    574574      Node target = _last[_sets.back().back()];
     
    577577          if (_tolerance.positive((*_capacity)[a])) {
    578578            Node u = _graph.source(a);
    579             _flow->set(a, (*_capacity)[a]);
    580             _excess->set(u, (*_excess)[u] + (*_capacity)[a]);
     579            (*_flow)[a] = (*_capacity)[a];
     580            (*_excess)[u] += (*_capacity)[a];
    581581            if (!(*_active)[u] && u != _source) {
    582582              activate(u);
     
    619619              }
    620620              if (!_tolerance.less(rem, excess)) {
    621                 _flow->set(a, (*_flow)[a] + excess);
    622                 _excess->set(v, (*_excess)[v] + excess);
     621                (*_flow)[a] += excess;
     622                (*_excess)[v] += excess;
    623623                excess = 0;
    624624                goto no_more_push;
    625625              } else {
    626626                excess -= rem;
    627                 _excess->set(v, (*_excess)[v] + rem);
    628                 _flow->set(a, (*_capacity)[a]);
     627                (*_excess)[v] += rem;
     628                (*_flow)[a] = (*_capacity)[a];
    629629              }
    630630            } else if (next_bucket > (*_bucket)[v]) {
     
    643643              }
    644644              if (!_tolerance.less(rem, excess)) {
    645                 _flow->set(a, (*_flow)[a] - excess);
    646                 _excess->set(v, (*_excess)[v] + excess);
     645                (*_flow)[a] -= excess;
     646                (*_excess)[v] += excess;
    647647                excess = 0;
    648648                goto no_more_push;
    649649              } else {
    650650                excess -= rem;
    651                 _excess->set(v, (*_excess)[v] + rem);
    652                 _flow->set(a, 0);
     651                (*_excess)[v] += rem;
     652                (*_flow)[a] = 0;
    653653              }
    654654            } else if (next_bucket > (*_bucket)[v]) {
     
    659659        no_more_push:
    660660
    661           _excess->set(n, excess);
     661          (*_excess)[n] = excess;
    662662
    663663          if (excess != 0) {
     
    677677            } else if (next_bucket == _node_num) {
    678678              _first[(*_bucket)[n]] = (*_next)[n];
    679               _prev->set((*_next)[n], INVALID);
     679              (*_prev)[(*_next)[n]] = INVALID;
    680680
    681681              std::list<std::list<int> >::iterator new_set =
     
    683683
    684684              new_set->push_front(bucket_num);
    685               _bucket->set(n, bucket_num);
     685              (*_bucket)[n] = bucket_num;
    686686              _first[bucket_num] = _last[bucket_num] = n;
    687               _next->set(n, INVALID);
    688               _prev->set(n, INVALID);
     687              (*_next)[n] = INVALID;
     688              (*_prev)[n] = INVALID;
    689689              _dormant[bucket_num] = true;
    690690              ++bucket_num;
     
    696696            } else {
    697697              _first[*_highest] = (*_next)[n];
    698               _prev->set((*_next)[n], INVALID);
     698              (*_prev)[(*_next)[n]] = INVALID;
    699699
    700700              while (next_bucket != *_highest) {
     
    709709              --_highest;
    710710
    711               _bucket->set(n, *_highest);
    712               _next->set(n, _first[*_highest]);
     711              (*_bucket)[n] = *_highest;
     712              (*_next)[n] = _first[*_highest];
    713713              if (_first[*_highest] != INVALID) {
    714                 _prev->set(_first[*_highest], n);
     714                (*_prev)[_first[*_highest]] = n;
    715715              } else {
    716716                _last[*_highest] = n;
     
    734734          _min_cut = (*_excess)[target];
    735735          for (NodeIt i(_graph); i != INVALID; ++i) {
    736             _min_cut_map->set(i, false);
     736            (*_min_cut_map)[i] = false;
    737737          }
    738738          for (std::list<int>::iterator it = _sets.back().begin();
     
    740740            Node n = _first[*it];
    741741            while (n != INVALID) {
    742               _min_cut_map->set(n, true);
     742              (*_min_cut_map)[n] = true;
    743743              n = (*_next)[n];
    744744            }
     
    753753              new_target = (*_prev)[target];
    754754            } else {
    755               _prev->set((*_next)[target], (*_prev)[target]);
     755              (*_prev)[(*_next)[target]] = (*_prev)[target];
    756756              new_target = (*_next)[target];
    757757            }
     
    759759              _first[(*_bucket)[target]] = (*_next)[target];
    760760            } else {
    761               _next->set((*_prev)[target], (*_next)[target]);
     761              (*_next)[(*_prev)[target]] = (*_next)[target];
    762762            }
    763763          } else {
     
    775775          }
    776776
    777           _bucket->set(target, 0);
    778 
    779           _source_set->set(target, true);
     777          (*_bucket)[target] = 0;
     778
     779          (*_source_set)[target] = true;
    780780          for (InArcIt a(_graph, target); a != INVALID; ++a) {
    781781            Value rem = (*_capacity)[a] - (*_flow)[a];
     
    785785              activate(v);
    786786            }
    787             _excess->set(v, (*_excess)[v] + rem);
    788             _flow->set(a, (*_capacity)[a]);
     787            (*_excess)[v] += rem;
     788            (*_flow)[a] = (*_capacity)[a];
    789789          }
    790790
     
    796796              activate(v);
    797797            }
    798             _excess->set(v, (*_excess)[v] + rem);
    799             _flow->set(a, 0);
     798            (*_excess)[v] += rem;
     799            (*_flow)[a] = 0;
    800800          }
    801801
Note: See TracChangeset for help on using the changeset viewer.