Changeset 2519:a7376f7ed899 in lemon-0.x for lemon/dinitz_sleator_tarjan.h

Timestamp:

11/21/07 14:35:10 (17 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3395

Message:

Changed queue implementation

File:

• lemon/dinitz_sleator_tarjan.h (modified) (5 diffs)

lemon/dinitz_sleator_tarjan.h

@@ -25 +25 @@
 /// and Tarjan.
 
-#include <lemon/time_measure.h>
-#include <queue>
 #include <lemon/graph_utils.h>
 #include <lemon/tolerance.h>
-#include <lemon/graph_adaptor.h>
-#include <lemon/bfs.h>
-#include <lemon/edge_set.h>
 #include <lemon/dynamic_tree.h>
 
@@ -161 +156 @@
     DynTree* _dt;
 
+    std::vector<Node> _queue;
+
     Tolerance _tolerance;
     
@@ -230 +227 @@
         _flow(0), _local_flow(false),
         _level(0), _dt_edges(0),
-        _dt_index(0), _dt(0),
+        _dt_index(0), _dt(0), _queue(),
         _tolerance(), _flow_value(), _max_value()
     {
@@ -327 +324 @@
         _dt_edges = new EdgeNodeMap(_graph);
       }
+      _queue.resize(countNodes(_graph));
       _max_value = _dt->maxValue();
     }
@@ -356 +354 @@
       int level = 0;
 
-      std::vector<Node> queue;
-      queue.push_back(_target);
+      _queue[0] = _target;
       _level->set(_target, level);
+
+      int first = 0, last = 1, limit = 0;
       
-      while ((*_level)[_source] == -2 && !queue.empty()) {
-        std::vector<Node> nqueue;
-        ++level;
+      while (first != last && (*_level)[_source] == -2) {
+        if (first == limit) {
+          limit = last;
+          ++level;
+        }
         
-        for (int i = 0; i < int(queue.size()); ++i) {
-          Node n = queue[i];
+        Node n = _queue[first++];
           
-          for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
-            Node v = _graph.target(e);
-            if ((*_level)[v] != -2) continue;
-            Value rem = (*_flow)[e];
-            if (!_tolerance.positive(rem)) continue;
-            _level->set(v, level);
-            nqueue.push_back(v);
-          }
-
-          for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
-            Node v = _graph.source(e);
-            if ((*_level)[v] != -2) continue;
-            Value rem = (*_capacity)[e] - (*_flow)[e];
-            if (!_tolerance.positive(rem)) continue;
-            _level->set(v, level);
-            nqueue.push_back(v);
-          }
-
-        }
-        queue.swap(nqueue);
-      }
-      
+        for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
+          Node v = _graph.target(e);
+          if ((*_level)[v] != -2) continue;
+          Value rem = (*_flow)[e];
+          if (!_tolerance.positive(rem)) continue;
+          _level->set(v, level);
+          _queue[last++] = v;
+        }
+        
+        for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
+          Node v = _graph.source(e);
+          if ((*_level)[v] != -2) continue;
+          Value rem = (*_capacity)[e] - (*_flow)[e];
+          if (!_tolerance.positive(rem)) continue;
+          _level->set(v, level);
+          _queue[last++] = v;
+        }
+      }
       return (*_level)[_source] != -2;
     }