Changeset 411:01c443515ad2 in lemon-main

Timestamp:

12/02/08 08:21:47 (16 years ago)

Author:

Balazs Dezso <deba@…>

Branch:

default

Phase:

public

Message:

New queue implementation for HaoOrlin? class (#58)

File:

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

lemon/hao_orlin.h

@@ -226 +226 @@
       }
 
-      int bucket_num = 1;
+      int bucket_num = 0;
+      std::vector<Node> queue(_node_num);
+      int qfirst = 0, qlast = 0, qsep = 0;
 
       {
@@ -232 +234 @@
 
         reached.set(_source, true);
-
         bool first_set = true;
 
@@ -238 +239 @@
           if (reached[t]) continue;
           _sets.push_front(std::list<int>());
-          _sets.front().push_front(bucket_num);
-          _dormant[bucket_num] = !first_set;
-
-          _bucket->set(t, bucket_num);
-          _first[bucket_num] = _last[bucket_num] = t;
-          _next->set(t, INVALID);
-          _prev->set(t, INVALID);
-
-          ++bucket_num;
-
-          std::vector<Node> queue;
-          queue.push_back(t);
+          
+          queue[qlast++] = t;
           reached.set(t, true);
 
-          while (!queue.empty()) {
-            _sets.front().push_front(bucket_num);
-            _dormant[bucket_num] = !first_set;
-            _first[bucket_num] = _last[bucket_num] = INVALID;
-
-            std::vector<Node> nqueue;
-            for (int i = 0; i < int(queue.size()); ++i) {
-              Node n = queue[i];
-              for (InArcIt a(_graph, n); a != INVALID; ++a) {
-                Node u = _graph.source(a);
-                if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
-                  reached.set(u, true);
-                  addItem(u, bucket_num);
-                  nqueue.push_back(u);
-                }
-              }
-            }
-            queue.swap(nqueue);
-            ++bucket_num;
-          }
-          _sets.front().pop_front();
-          --bucket_num;
+          while (qfirst != qlast) {
+            if (qsep == qfirst) {
+              ++bucket_num;
+              _sets.front().push_front(bucket_num);
+              _dormant[bucket_num] = !first_set;
+              _first[bucket_num] = _last[bucket_num] = INVALID;
+              qsep = qlast;
+            }
+
+            Node n = queue[qfirst++];
+            addItem(n, bucket_num);
+
+            for (InArcIt a(_graph, n); a != INVALID; ++a) {
+              Node u = _graph.source(a);
+              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
+                reached.set(u, true);
+                queue[qlast++] = u;
+              }
+            }
+          }
           first_set = false;
         }
 
+        ++bucket_num;
         _bucket->set(_source, 0);
         _dormant[0] = true;
@@ -535 +525 @@
       }
 
-      int bucket_num = 1;
+      int bucket_num = 0;
+      std::vector<Node> queue(_node_num);
+      int qfirst = 0, qlast = 0, qsep = 0;
 
       {
@@ -547 +539 @@
           if (reached[t]) continue;
           _sets.push_front(std::list<int>());
-          _sets.front().push_front(bucket_num);
-          _dormant[bucket_num] = !first_set;
-
-          _bucket->set(t, bucket_num);
-          _first[bucket_num] = _last[bucket_num] = t;
-          _next->set(t, INVALID);
-          _prev->set(t, INVALID);
-
-          ++bucket_num;
-
-          std::vector<Node> queue;
-          queue.push_back(t);
+          
+          queue[qlast++] = t;
           reached.set(t, true);
 
-          while (!queue.empty()) {
-            _sets.front().push_front(bucket_num);
-            _dormant[bucket_num] = !first_set;
-            _first[bucket_num] = _last[bucket_num] = INVALID;
-
-            std::vector<Node> nqueue;
-            for (int i = 0; i < int(queue.size()); ++i) {
-              Node n = queue[i];
-              for (OutArcIt a(_graph, n); a != INVALID; ++a) {
-                Node u = _graph.target(a);
-                if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
-                  reached.set(u, true);
-                  addItem(u, bucket_num);
-                  nqueue.push_back(u);
-                }
-              }
-            }
-            queue.swap(nqueue);
-            ++bucket_num;
-          }
-          _sets.front().pop_front();
-          --bucket_num;
+          while (qfirst != qlast) {
+            if (qsep == qfirst) {
+              ++bucket_num;
+              _sets.front().push_front(bucket_num);
+              _dormant[bucket_num] = !first_set;
+              _first[bucket_num] = _last[bucket_num] = INVALID;
+              qsep = qlast;
+            }
+
+            Node n = queue[qfirst++];
+            addItem(n, bucket_num);
+
+            for (OutArcIt a(_graph, n); a != INVALID; ++a) {
+              Node u = _graph.target(a);
+              if (!reached[u] && _tolerance.positive((*_capacity)[a])) {
+                reached.set(u, true);
+                queue[qlast++] = u;
+              }
+            }
+          }
           first_set = false;
         }
 
+        ++bucket_num;
         _bucket->set(_source, 0);
         _dormant[0] = true;
@@ -865 +846 @@
       _node_num = countNodes(_graph);
 
-      _first.resize(_node_num + 1);
-      _last.resize(_node_num + 1);
-
-      _dormant.resize(_node_num + 1);
+      _first.resize(_node_num);
+      _last.resize(_node_num);
+
+      _dormant.resize(_node_num);
 
       if (!_flow) {