Changeset 2519:a7376f7ed899 in lemon-0.x

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

Location:

lemon

Files:

• dinitz_sleator_tarjan.h (modified) (5 diffs)
• dynamic_tree.h (modified) (12 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;
     }

lemon/dynamic_tree.h

@@ -144 +144 @@
     /// \brief Add \e x value to the cost of every node on the path from
     /// \e item to findRoot(item).
-    void addCost(const Item &item, Value x){
+    void addCost(const Item &item, Value x) {
       addPathCost(expose(_iim[item]), x);
     }
@@ -201 +201 @@
     }
 
-    int findPath(int v){
+    int findPath(int v) {
       splay(v);
       return v;
     }
     
-    int findPathCost(int p, Value &d){
+    int findPathCost(int p, Value &d) {
       while ((_data[p].right != -1 && 
               !_tolerance.less(0, _data[_data[p].right].dmin)) || 
@@ -214 +214 @@
           p = _data[p].right;
         } else if (_data[p].left != -1 && 
-                   !_tolerance.less(0, _data[_data[p].left].dmin)){
+                   !_tolerance.less(0, _data[_data[p].left].dmin)) {
           p = _data[p].left;
         }
@@ -231 +231 @@
     }
     
-    void addPathCost(int p, Value x){
+    void addPathCost(int p, Value x) {
       if (!_tolerance.less(x, _max_value)) {
-        _data[p].dmin = x;_data[p].dcost = x;
+        _data[p].dmin = x;
+        _data[p].dcost = x;
       } else if (!_tolerance.less(-x, _max_value)) {
         _data[p].dmin = 0;
@@ -364 +365 @@
       Value aa = _data[a].dcost;
       if (_tolerance.less(aa, _max_value)) { 
-        aa+= min;
+        aa += min;
       }
 
@@ -372 +373 @@
       Value bb = _data[b].dcost;
       if (_tolerance.less(bb, _max_value)) { 
-        bb+= ab;
+        bb += ab;
       }
 
@@ -381 +382 @@
         cc = _data[c].dmin;
         if (_tolerance.less(cc, _max_value)) {
-          cc+=min;
+          cc += min;
         }
       }
@@ -687 +688 @@
     }
 
-    int findPath(int v){
+    int findPath(int v) {
       splay(v);
       return v;
     }
     
-    int findPathCost(int p, Value &d){
+    int findPathCost(int p, Value &d) {
       while ((_data[p].right != -1 && 
               !_tolerance.less(0, _data[_data[p].right].dmin)) || 
@@ -709 +710 @@
     }
 
-    int findTail(int p){
+    int findTail(int p) {
       while (_data[p].right != -1) {
         p = _data[p].right;
@@ -717 +718 @@
     }
     
-    void addPathCost(int p, Value x){
+    void addPathCost(int p, Value x) {
       if (!_tolerance.less(x, _max_value)) {
         _data[p].dmin = x;_data[p].dcost = x;
@@ -756 +757 @@
         _data[p].dmin -= min;
       }
-      if (q!=-1){
+      if (q != -1){
         _data[q].parent = v;
         if (_tolerance.less(_data[q].dmin,_max_value)) {
@@ -764 +765 @@
       _data[v].left = p;
       _data[v].right = q;
-      if (_tolerance.less(min,_max_value)) {
+      if (_tolerance.less(min, _max_value)) {
         _data[v].dcost = _data[v].dmin - min;
       }