COIN-OR::LEMON - Graph Library

Changeset 411:01c443515ad2 in lemon-1.2 for lemon


Ignore:
Timestamp:
12/02/08 08:21:47 (15 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Phase:
public
Message:

New queue implementation for HaoOrlin? class (#58)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/hao_orlin.h

    r409 r411  
    226226      }
    227227
    228       int bucket_num = 1;
     228      int bucket_num = 0;
     229      std::vector<Node> queue(_node_num);
     230      int qfirst = 0, qlast = 0, qsep = 0;
    229231
    230232      {
     
    232234
    233235        reached.set(_source, true);
    234 
    235236        bool first_set = true;
    236237
     
    238239          if (reached[t]) continue;
    239240          _sets.push_front(std::list<int>());
    240           _sets.front().push_front(bucket_num);
    241           _dormant[bucket_num] = !first_set;
    242 
    243           _bucket->set(t, bucket_num);
    244           _first[bucket_num] = _last[bucket_num] = t;
    245           _next->set(t, INVALID);
    246           _prev->set(t, INVALID);
    247 
    248           ++bucket_num;
    249 
    250           std::vector<Node> queue;
    251           queue.push_back(t);
     241         
     242          queue[qlast++] = t;
    252243          reached.set(t, true);
    253244
    254           while (!queue.empty()) {
    255             _sets.front().push_front(bucket_num);
    256             _dormant[bucket_num] = !first_set;
    257             _first[bucket_num] = _last[bucket_num] = INVALID;
    258 
    259             std::vector<Node> nqueue;
    260             for (int i = 0; i < int(queue.size()); ++i) {
    261               Node n = queue[i];
    262               for (InArcIt a(_graph, n); a != INVALID; ++a) {
    263                 Node u = _graph.source(a);
    264                 if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
    265                   reached.set(u, true);
    266                   addItem(u, bucket_num);
    267                   nqueue.push_back(u);
    268                 }
    269               }
    270             }
    271             queue.swap(nqueue);
    272             ++bucket_num;
    273           }
    274           _sets.front().pop_front();
    275           --bucket_num;
     245          while (qfirst != qlast) {
     246            if (qsep == qfirst) {
     247              ++bucket_num;
     248              _sets.front().push_front(bucket_num);
     249              _dormant[bucket_num] = !first_set;
     250              _first[bucket_num] = _last[bucket_num] = INVALID;
     251              qsep = qlast;
     252            }
     253
     254            Node n = queue[qfirst++];
     255            addItem(n, bucket_num);
     256
     257            for (InArcIt a(_graph, n); a != INVALID; ++a) {
     258              Node u = _graph.source(a);
     259              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
     260                reached.set(u, true);
     261                queue[qlast++] = u;
     262              }
     263            }
     264          }
    276265          first_set = false;
    277266        }
    278267
     268        ++bucket_num;
    279269        _bucket->set(_source, 0);
    280270        _dormant[0] = true;
     
    535525      }
    536526
    537       int bucket_num = 1;
     527      int bucket_num = 0;
     528      std::vector<Node> queue(_node_num);
     529      int qfirst = 0, qlast = 0, qsep = 0;
    538530
    539531      {
     
    547539          if (reached[t]) continue;
    548540          _sets.push_front(std::list<int>());
    549           _sets.front().push_front(bucket_num);
    550           _dormant[bucket_num] = !first_set;
    551 
    552           _bucket->set(t, bucket_num);
    553           _first[bucket_num] = _last[bucket_num] = t;
    554           _next->set(t, INVALID);
    555           _prev->set(t, INVALID);
    556 
    557           ++bucket_num;
    558 
    559           std::vector<Node> queue;
    560           queue.push_back(t);
     541         
     542          queue[qlast++] = t;
    561543          reached.set(t, true);
    562544
    563           while (!queue.empty()) {
    564             _sets.front().push_front(bucket_num);
    565             _dormant[bucket_num] = !first_set;
    566             _first[bucket_num] = _last[bucket_num] = INVALID;
    567 
    568             std::vector<Node> nqueue;
    569             for (int i = 0; i < int(queue.size()); ++i) {
    570               Node n = queue[i];
    571               for (OutArcIt a(_graph, n); a != INVALID; ++a) {
    572                 Node u = _graph.target(a);
    573                 if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
    574                   reached.set(u, true);
    575                   addItem(u, bucket_num);
    576                   nqueue.push_back(u);
    577                 }
    578               }
    579             }
    580             queue.swap(nqueue);
    581             ++bucket_num;
    582           }
    583           _sets.front().pop_front();
    584           --bucket_num;
     545          while (qfirst != qlast) {
     546            if (qsep == qfirst) {
     547              ++bucket_num;
     548              _sets.front().push_front(bucket_num);
     549              _dormant[bucket_num] = !first_set;
     550              _first[bucket_num] = _last[bucket_num] = INVALID;
     551              qsep = qlast;
     552            }
     553
     554            Node n = queue[qfirst++];
     555            addItem(n, bucket_num);
     556
     557            for (OutArcIt a(_graph, n); a != INVALID; ++a) {
     558              Node u = _graph.target(a);
     559              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
     560                reached.set(u, true);
     561                queue[qlast++] = u;
     562              }
     563            }
     564          }
    585565          first_set = false;
    586566        }
    587567
     568        ++bucket_num;
    588569        _bucket->set(_source, 0);
    589570        _dormant[0] = true;
     
    865846      _node_num = countNodes(_graph);
    866847
    867       _first.resize(_node_num + 1);
    868       _last.resize(_node_num + 1);
    869 
    870       _dormant.resize(_node_num + 1);
     848      _first.resize(_node_num);
     849      _last.resize(_node_num);
     850
     851      _dormant.resize(_node_num);
    871852
    872853      if (!_flow) {
Note: See TracChangeset for help on using the changeset viewer.