# HG changeset patch # User deba # Date 1195652110 0 # Node ID a7376f7ed8991a315a1f2becec645d6167dfe433 # Parent 4c0a23bd70b521cb070e43992d53ff02111576d1 Changed queue implementation diff -r 4c0a23bd70b5 -r a7376f7ed899 lemon/dinitz_sleator_tarjan.h --- a/lemon/dinitz_sleator_tarjan.h Wed Nov 21 13:34:38 2007 +0000 +++ b/lemon/dinitz_sleator_tarjan.h Wed Nov 21 13:35:10 2007 +0000 @@ -24,13 +24,8 @@ /// \brief Implementation the dynamic tree data structure of Sleator /// and Tarjan. -#include -#include #include #include -#include -#include -#include #include #include @@ -160,6 +155,8 @@ IntNodeMap* _dt_index; DynTree* _dt; + std::vector _queue; + Tolerance _tolerance; Value _flow_value; @@ -229,7 +226,7 @@ _source(source), _target(target), _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() { if (_source == _target) { @@ -326,6 +323,7 @@ if (!_dt_edges) { _dt_edges = new EdgeNodeMap(_graph); } + _queue.resize(countNodes(_graph)); _max_value = _dt->maxValue(); } @@ -355,39 +353,37 @@ int level = 0; - std::vector 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 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); - } - + 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; } - queue.swap(nqueue); + + 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; } diff -r 4c0a23bd70b5 -r a7376f7ed899 lemon/dynamic_tree.h --- a/lemon/dynamic_tree.h Wed Nov 21 13:34:38 2007 +0000 +++ b/lemon/dynamic_tree.h Wed Nov 21 13:35:10 2007 +0000 @@ -143,7 +143,7 @@ /// \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); } @@ -200,12 +200,12 @@ return _iim[item]; } - 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)) || (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) { @@ -213,7 +213,7 @@ !_tolerance.less(0, _data[_data[p].right].dmin)) { 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; } } @@ -230,9 +230,10 @@ return p; } - 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; _data[p].dcost = 0; @@ -363,7 +364,7 @@ Value aa = _data[a].dcost; if (_tolerance.less(aa, _max_value)) { - aa+= min; + aa += min; } @@ -371,7 +372,7 @@ Value ab = min + _data[b].dmin; Value bb = _data[b].dcost; if (_tolerance.less(bb, _max_value)) { - bb+= ab; + bb += ab; } int c = -1; @@ -380,7 +381,7 @@ c = _data[a].right; cc = _data[c].dmin; if (_tolerance.less(cc, _max_value)) { - cc+=min; + cc += min; } } @@ -686,12 +687,12 @@ return _iim[item]; } - 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)) || (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) { @@ -708,7 +709,7 @@ return p; } - int findTail(int p){ + int findTail(int p) { while (_data[p].right != -1) { p = _data[p].right; } @@ -716,7 +717,7 @@ return p; } - 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; } else if (!_tolerance.less(-x, _max_value)) { @@ -755,7 +756,7 @@ _data[p].parent = v; _data[p].dmin -= min; } - if (q!=-1){ + if (q != -1){ _data[q].parent = v; if (_tolerance.less(_data[q].dmin,_max_value)) { _data[q].dmin -= min; @@ -763,7 +764,7 @@ } _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; } _data[v].dmin = min;