1.1 --- a/lemon/dinitz_sleator_tarjan.h	Wed Nov 21 13:34:38 2007 +0000
     1.2 +++ b/lemon/dinitz_sleator_tarjan.h	Wed Nov 21 13:35:10 2007 +0000
     1.3 @@ -24,13 +24,8 @@
     1.4  /// \brief Implementation the dynamic tree data structure of Sleator
     1.5  /// and Tarjan.
     1.6  
     1.7 -#include <lemon/time_measure.h>
     1.8 -#include <queue>
     1.9  #include <lemon/graph_utils.h>
    1.10  #include <lemon/tolerance.h>
    1.11 -#include <lemon/graph_adaptor.h>
    1.12 -#include <lemon/bfs.h>
    1.13 -#include <lemon/edge_set.h>
    1.14  #include <lemon/dynamic_tree.h>
    1.15  
    1.16  #include <vector>
    1.17 @@ -160,6 +155,8 @@
    1.18      IntNodeMap* _dt_index;
    1.19      DynTree* _dt;
    1.20  
    1.21 +    std::vector<Node> _queue;
    1.22 +
    1.23      Tolerance _tolerance;
    1.24      
    1.25      Value _flow_value;
    1.26 @@ -229,7 +226,7 @@
    1.27  	_source(source), _target(target),
    1.28  	_flow(0), _local_flow(false),
    1.29  	_level(0), _dt_edges(0),
    1.30 -	_dt_index(0), _dt(0),
    1.31 +	_dt_index(0), _dt(0), _queue(),
    1.32  	_tolerance(), _flow_value(), _max_value()
    1.33      {
    1.34        if (_source == _target) {
    1.35 @@ -326,6 +323,7 @@
    1.36        if (!_dt_edges) {
    1.37  	_dt_edges = new EdgeNodeMap(_graph);
    1.38        }
    1.39 +      _queue.resize(countNodes(_graph));
    1.40        _max_value = _dt->maxValue();
    1.41      }
    1.42  
    1.43 @@ -355,39 +353,37 @@
    1.44        
    1.45        int level = 0;
    1.46  
    1.47 -      std::vector<Node> queue;
    1.48 -      queue.push_back(_target);
    1.49 +      _queue[0] = _target;
    1.50        _level->set(_target, level);
    1.51 +
    1.52 +      int first = 0, last = 1, limit = 0;
    1.53        
    1.54 -      while ((*_level)[_source] == -2 && !queue.empty()) {
    1.55 -	std::vector<Node> nqueue;
    1.56 -	++level;
    1.57 +      while (first != last && (*_level)[_source] == -2) {
    1.58 +	if (first == limit) {
    1.59 +	  limit = last;
    1.60 +	  ++level;
    1.61 +	}
    1.62  	
    1.63 -	for (int i = 0; i < int(queue.size()); ++i) {
    1.64 -	  Node n = queue[i];
    1.65 +	Node n = _queue[first++];
    1.66  	  
    1.67 -	  for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
    1.68 -	    Node v = _graph.target(e);
    1.69 -	    if ((*_level)[v] != -2) continue;
    1.70 -	    Value rem = (*_flow)[e];
    1.71 -	    if (!_tolerance.positive(rem)) continue;
    1.72 -	    _level->set(v, level);
    1.73 -	    nqueue.push_back(v);
    1.74 -	  }
    1.75 -
    1.76 -	  for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
    1.77 -	    Node v = _graph.source(e);
    1.78 -	    if ((*_level)[v] != -2) continue;
    1.79 -	    Value rem = (*_capacity)[e] - (*_flow)[e];
    1.80 -	    if (!_tolerance.positive(rem)) continue;
    1.81 -	    _level->set(v, level);
    1.82 -	    nqueue.push_back(v);
    1.83 -	  }
    1.84 -
    1.85 +	for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
    1.86 +	  Node v = _graph.target(e);
    1.87 +	  if ((*_level)[v] != -2) continue;
    1.88 +	  Value rem = (*_flow)[e];
    1.89 +	  if (!_tolerance.positive(rem)) continue;
    1.90 +	  _level->set(v, level);
    1.91 +	  _queue[last++] = v;
    1.92  	}
    1.93 -	queue.swap(nqueue);
    1.94 +	
    1.95 +	for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
    1.96 +	  Node v = _graph.source(e);
    1.97 +	  if ((*_level)[v] != -2) continue;
    1.98 +	  Value rem = (*_capacity)[e] - (*_flow)[e];
    1.99 +	  if (!_tolerance.positive(rem)) continue;
   1.100 +	  _level->set(v, level);
   1.101 +	  _queue[last++] = v;
   1.102 +	}
   1.103        }
   1.104 -      
   1.105        return (*_level)[_source] != -2;
   1.106      }
   1.107  

     2.1 --- a/lemon/dynamic_tree.h	Wed Nov 21 13:34:38 2007 +0000
     2.2 +++ b/lemon/dynamic_tree.h	Wed Nov 21 13:35:10 2007 +0000
     2.3 @@ -143,7 +143,7 @@
     2.4      
     2.5      /// \brief Add \e x value to the cost of every node on the path from
     2.6      /// \e item to findRoot(item).
     2.7 -    void addCost(const Item &item, Value x){
     2.8 +    void addCost(const Item &item, Value x) {
     2.9        addPathCost(expose(_iim[item]), x);
    2.10      }
    2.11      
    2.12 @@ -200,12 +200,12 @@
    2.13        return _iim[item];
    2.14      }
    2.15  
    2.16 -    int findPath(int v){
    2.17 +    int findPath(int v) {
    2.18        splay(v);
    2.19        return v;
    2.20      }
    2.21      
    2.22 -    int findPathCost(int p, Value &d){
    2.23 +    int findPathCost(int p, Value &d) {
    2.24        while ((_data[p].right != -1 && 
    2.25  	      !_tolerance.less(0, _data[_data[p].right].dmin)) || 
    2.26  	     (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
    2.27 @@ -213,7 +213,7 @@
    2.28  	    !_tolerance.less(0, _data[_data[p].right].dmin)) {
    2.29  	  p = _data[p].right;
    2.30  	} else if (_data[p].left != -1 && 
    2.31 -		   !_tolerance.less(0, _data[_data[p].left].dmin)){
    2.32 +		   !_tolerance.less(0, _data[_data[p].left].dmin)) {
    2.33  	  p = _data[p].left;
    2.34  	}
    2.35        }
    2.36 @@ -230,9 +230,10 @@
    2.37        return p;
    2.38      }
    2.39      
    2.40 -    void addPathCost(int p, Value x){
    2.41 +    void addPathCost(int p, Value x) {
    2.42        if (!_tolerance.less(x, _max_value)) {
    2.43 -	_data[p].dmin = x;_data[p].dcost = x;
    2.44 +	_data[p].dmin = x;
    2.45 +	_data[p].dcost = x;
    2.46        } else if (!_tolerance.less(-x, _max_value)) {
    2.47  	_data[p].dmin = 0;
    2.48  	_data[p].dcost = 0;
    2.49 @@ -363,7 +364,7 @@
    2.50          
    2.51        Value aa = _data[a].dcost;
    2.52        if (_tolerance.less(aa, _max_value)) { 
    2.53 -	aa+= min;
    2.54 +	aa += min;
    2.55        }
    2.56  
    2.57  
    2.58 @@ -371,7 +372,7 @@
    2.59        Value ab = min + _data[b].dmin;
    2.60        Value bb = _data[b].dcost;
    2.61        if (_tolerance.less(bb, _max_value)) { 
    2.62 -	bb+= ab;
    2.63 +	bb += ab;
    2.64        }
    2.65  
    2.66        int c = -1;
    2.67 @@ -380,7 +381,7 @@
    2.68  	c = _data[a].right;
    2.69  	cc = _data[c].dmin;
    2.70  	if (_tolerance.less(cc, _max_value)) {
    2.71 -	  cc+=min;
    2.72 +	  cc += min;
    2.73  	}
    2.74        }
    2.75  
    2.76 @@ -686,12 +687,12 @@
    2.77        return _iim[item];
    2.78      }
    2.79  
    2.80 -    int findPath(int v){
    2.81 +    int findPath(int v) {
    2.82        splay(v);
    2.83        return v;
    2.84      }
    2.85      
    2.86 -    int findPathCost(int p, Value &d){
    2.87 +    int findPathCost(int p, Value &d) {
    2.88        while ((_data[p].right != -1 && 
    2.89  	      !_tolerance.less(0, _data[_data[p].right].dmin)) || 
    2.90  	     (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
    2.91 @@ -708,7 +709,7 @@
    2.92        return p; 
    2.93      }
    2.94  
    2.95 -    int findTail(int p){
    2.96 +    int findTail(int p) {
    2.97        while (_data[p].right != -1) {
    2.98  	p = _data[p].right;
    2.99        }
   2.100 @@ -716,7 +717,7 @@
   2.101        return p;
   2.102      }
   2.103      
   2.104 -    void addPathCost(int p, Value x){
   2.105 +    void addPathCost(int p, Value x) {
   2.106        if (!_tolerance.less(x, _max_value)) {
   2.107  	_data[p].dmin = x;_data[p].dcost = x;
   2.108        } else if (!_tolerance.less(-x, _max_value)) {
   2.109 @@ -755,7 +756,7 @@
   2.110  	_data[p].parent = v;
   2.111  	_data[p].dmin -= min;
   2.112        }
   2.113 -      if (q!=-1){
   2.114 +      if (q != -1){
   2.115  	_data[q].parent = v;
   2.116  	if (_tolerance.less(_data[q].dmin,_max_value)) {
   2.117  	  _data[q].dmin -= min;
   2.118 @@ -763,7 +764,7 @@
   2.119        }
   2.120        _data[v].left = p;
   2.121        _data[v].right = q;
   2.122 -      if (_tolerance.less(min,_max_value)) {
   2.123 +      if (_tolerance.less(min, _max_value)) {
   2.124  	_data[v].dcost = _data[v].dmin - min;
   2.125        }
   2.126        _data[v].dmin = min;