New queue implementation for HaoOrlin class (#58)
authorBalazs Dezso <deba@inf.elte.hu>
Tue, 02 Dec 2008 08:21:47 +0100
changeset 41101c443515ad2
parent 410 eac19fb31a09
child 412 7030149efed2
New queue implementation for HaoOrlin class (#58)
lemon/hao_orlin.h
     1.1 --- a/lemon/hao_orlin.h	Mon Dec 01 23:15:15 2008 +0100
     1.2 +++ b/lemon/hao_orlin.h	Tue Dec 02 08:21:47 2008 +0100
     1.3 @@ -225,57 +225,47 @@
     1.4          _flow->set(a, 0);
     1.5        }
     1.6  
     1.7 -      int bucket_num = 1;
     1.8 +      int bucket_num = 0;
     1.9 +      std::vector<Node> queue(_node_num);
    1.10 +      int qfirst = 0, qlast = 0, qsep = 0;
    1.11  
    1.12        {
    1.13          typename Digraph::template NodeMap<bool> reached(_graph, false);
    1.14  
    1.15          reached.set(_source, true);
    1.16 -
    1.17          bool first_set = true;
    1.18  
    1.19          for (NodeIt t(_graph); t != INVALID; ++t) {
    1.20            if (reached[t]) continue;
    1.21            _sets.push_front(std::list<int>());
    1.22 -          _sets.front().push_front(bucket_num);
    1.23 -          _dormant[bucket_num] = !first_set;
    1.24 -
    1.25 -          _bucket->set(t, bucket_num);
    1.26 -          _first[bucket_num] = _last[bucket_num] = t;
    1.27 -          _next->set(t, INVALID);
    1.28 -          _prev->set(t, INVALID);
    1.29 -
    1.30 -          ++bucket_num;
    1.31 -
    1.32 -          std::vector<Node> queue;
    1.33 -          queue.push_back(t);
    1.34 +          
    1.35 +          queue[qlast++] = t;
    1.36            reached.set(t, true);
    1.37  
    1.38 -          while (!queue.empty()) {
    1.39 -            _sets.front().push_front(bucket_num);
    1.40 -            _dormant[bucket_num] = !first_set;
    1.41 -            _first[bucket_num] = _last[bucket_num] = INVALID;
    1.42 +          while (qfirst != qlast) {
    1.43 +            if (qsep == qfirst) {
    1.44 +              ++bucket_num;
    1.45 +              _sets.front().push_front(bucket_num);
    1.46 +              _dormant[bucket_num] = !first_set;
    1.47 +              _first[bucket_num] = _last[bucket_num] = INVALID;
    1.48 +              qsep = qlast;
    1.49 +            }
    1.50  
    1.51 -            std::vector<Node> nqueue;
    1.52 -            for (int i = 0; i < int(queue.size()); ++i) {
    1.53 -              Node n = queue[i];
    1.54 -              for (InArcIt a(_graph, n); a != INVALID; ++a) {
    1.55 -                Node u = _graph.source(a);
    1.56 -                if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
    1.57 -                  reached.set(u, true);
    1.58 -                  addItem(u, bucket_num);
    1.59 -                  nqueue.push_back(u);
    1.60 -                }
    1.61 +            Node n = queue[qfirst++];
    1.62 +            addItem(n, bucket_num);
    1.63 +
    1.64 +            for (InArcIt a(_graph, n); a != INVALID; ++a) {
    1.65 +              Node u = _graph.source(a);
    1.66 +              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
    1.67 +                reached.set(u, true);
    1.68 +                queue[qlast++] = u;
    1.69                }
    1.70              }
    1.71 -            queue.swap(nqueue);
    1.72 -            ++bucket_num;
    1.73            }
    1.74 -          _sets.front().pop_front();
    1.75 -          --bucket_num;
    1.76            first_set = false;
    1.77          }
    1.78  
    1.79 +        ++bucket_num;
    1.80          _bucket->set(_source, 0);
    1.81          _dormant[0] = true;
    1.82        }
    1.83 @@ -534,7 +524,9 @@
    1.84          _flow->set(a, 0);
    1.85        }
    1.86  
    1.87 -      int bucket_num = 1;
    1.88 +      int bucket_num = 0;
    1.89 +      std::vector<Node> queue(_node_num);
    1.90 +      int qfirst = 0, qlast = 0, qsep = 0;
    1.91  
    1.92        {
    1.93          typename Digraph::template NodeMap<bool> reached(_graph, false);
    1.94 @@ -546,45 +538,34 @@
    1.95          for (NodeIt t(_graph); t != INVALID; ++t) {
    1.96            if (reached[t]) continue;
    1.97            _sets.push_front(std::list<int>());
    1.98 -          _sets.front().push_front(bucket_num);
    1.99 -          _dormant[bucket_num] = !first_set;
   1.100 -
   1.101 -          _bucket->set(t, bucket_num);
   1.102 -          _first[bucket_num] = _last[bucket_num] = t;
   1.103 -          _next->set(t, INVALID);
   1.104 -          _prev->set(t, INVALID);
   1.105 -
   1.106 -          ++bucket_num;
   1.107 -
   1.108 -          std::vector<Node> queue;
   1.109 -          queue.push_back(t);
   1.110 +          
   1.111 +          queue[qlast++] = t;
   1.112            reached.set(t, true);
   1.113  
   1.114 -          while (!queue.empty()) {
   1.115 -            _sets.front().push_front(bucket_num);
   1.116 -            _dormant[bucket_num] = !first_set;
   1.117 -            _first[bucket_num] = _last[bucket_num] = INVALID;
   1.118 +          while (qfirst != qlast) {
   1.119 +            if (qsep == qfirst) {
   1.120 +              ++bucket_num;
   1.121 +              _sets.front().push_front(bucket_num);
   1.122 +              _dormant[bucket_num] = !first_set;
   1.123 +              _first[bucket_num] = _last[bucket_num] = INVALID;
   1.124 +              qsep = qlast;
   1.125 +            }
   1.126  
   1.127 -            std::vector<Node> nqueue;
   1.128 -            for (int i = 0; i < int(queue.size()); ++i) {
   1.129 -              Node n = queue[i];
   1.130 -              for (OutArcIt a(_graph, n); a != INVALID; ++a) {
   1.131 -                Node u = _graph.target(a);
   1.132 -                if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
   1.133 -                  reached.set(u, true);
   1.134 -                  addItem(u, bucket_num);
   1.135 -                  nqueue.push_back(u);
   1.136 -                }
   1.137 +            Node n = queue[qfirst++];
   1.138 +            addItem(n, bucket_num);
   1.139 +
   1.140 +            for (OutArcIt a(_graph, n); a != INVALID; ++a) {
   1.141 +              Node u = _graph.target(a);
   1.142 +              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
   1.143 +                reached.set(u, true);
   1.144 +                queue[qlast++] = u;
   1.145                }
   1.146              }
   1.147 -            queue.swap(nqueue);
   1.148 -            ++bucket_num;
   1.149            }
   1.150 -          _sets.front().pop_front();
   1.151 -          --bucket_num;
   1.152            first_set = false;
   1.153          }
   1.154  
   1.155 +        ++bucket_num;
   1.156          _bucket->set(_source, 0);
   1.157          _dormant[0] = true;
   1.158        }
   1.159 @@ -864,10 +845,10 @@
   1.160  
   1.161        _node_num = countNodes(_graph);
   1.162  
   1.163 -      _first.resize(_node_num + 1);
   1.164 -      _last.resize(_node_num + 1);
   1.165 +      _first.resize(_node_num);
   1.166 +      _last.resize(_node_num);
   1.167  
   1.168 -      _dormant.resize(_node_num + 1);
   1.169 +      _dormant.resize(_node_num);
   1.170  
   1.171        if (!_flow) {
   1.172          _flow = new FlowMap(_graph);