Changeset 2519:a7376f7ed899 in lemon0.x
 Timestamp:
 11/21/07 14:35:10 (12 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3395
 Location:
 lemon
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/dinitz_sleator_tarjan.h
r2514 r2519 25 25 /// and Tarjan. 26 26 27 #include <lemon/time_measure.h>28 #include <queue>29 27 #include <lemon/graph_utils.h> 30 28 #include <lemon/tolerance.h> 31 #include <lemon/graph_adaptor.h>32 #include <lemon/bfs.h>33 #include <lemon/edge_set.h>34 29 #include <lemon/dynamic_tree.h> 35 30 … … 161 156 DynTree* _dt; 162 157 158 std::vector<Node> _queue; 159 163 160 Tolerance _tolerance; 164 161 … … 230 227 _flow(0), _local_flow(false), 231 228 _level(0), _dt_edges(0), 232 _dt_index(0), _dt(0), 229 _dt_index(0), _dt(0), _queue(), 233 230 _tolerance(), _flow_value(), _max_value() 234 231 { … … 327 324 _dt_edges = new EdgeNodeMap(_graph); 328 325 } 326 _queue.resize(countNodes(_graph)); 329 327 _max_value = _dt>maxValue(); 330 328 } … … 356 354 int level = 0; 357 355 358 std::vector<Node> queue; 359 queue.push_back(_target); 356 _queue[0] = _target; 360 357 _level>set(_target, level); 358 359 int first = 0, last = 1, limit = 0; 361 360 362 while ((*_level)[_source] == 2 && !queue.empty()) { 363 std::vector<Node> nqueue; 364 ++level; 361 while (first != last && (*_level)[_source] == 2) { 362 if (first == limit) { 363 limit = last; 364 ++level; 365 } 365 366 366 for (int i = 0; i < int(queue.size()); ++i) { 367 Node n = queue[i]; 367 Node n = _queue[first++]; 368 368 369 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) { 370 Node v = _graph.target(e); 371 if ((*_level)[v] != 2) continue; 372 Value rem = (*_flow)[e]; 373 if (!_tolerance.positive(rem)) continue; 374 _level>set(v, level); 375 nqueue.push_back(v); 376 } 377 378 for (InEdgeIt e(_graph, n); e != INVALID; ++e) { 379 Node v = _graph.source(e); 380 if ((*_level)[v] != 2) continue; 381 Value rem = (*_capacity)[e]  (*_flow)[e]; 382 if (!_tolerance.positive(rem)) continue; 383 _level>set(v, level); 384 nqueue.push_back(v); 385 } 386 387 } 388 queue.swap(nqueue); 389 } 390 369 for (OutEdgeIt e(_graph, n); e != INVALID; ++e) { 370 Node v = _graph.target(e); 371 if ((*_level)[v] != 2) continue; 372 Value rem = (*_flow)[e]; 373 if (!_tolerance.positive(rem)) continue; 374 _level>set(v, level); 375 _queue[last++] = v; 376 } 377 378 for (InEdgeIt e(_graph, n); e != INVALID; ++e) { 379 Node v = _graph.source(e); 380 if ((*_level)[v] != 2) continue; 381 Value rem = (*_capacity)[e]  (*_flow)[e]; 382 if (!_tolerance.positive(rem)) continue; 383 _level>set(v, level); 384 _queue[last++] = v; 385 } 386 } 391 387 return (*_level)[_source] != 2; 392 388 } 
lemon/dynamic_tree.h
r2514 r2519 144 144 /// \brief Add \e x value to the cost of every node on the path from 145 145 /// \e item to findRoot(item). 146 void addCost(const Item &item, Value x) {146 void addCost(const Item &item, Value x) { 147 147 addPathCost(expose(_iim[item]), x); 148 148 } … … 201 201 } 202 202 203 int findPath(int v) {203 int findPath(int v) { 204 204 splay(v); 205 205 return v; 206 206 } 207 207 208 int findPathCost(int p, Value &d) {208 int findPathCost(int p, Value &d) { 209 209 while ((_data[p].right != 1 && 210 210 !_tolerance.less(0, _data[_data[p].right].dmin))  … … 214 214 p = _data[p].right; 215 215 } else if (_data[p].left != 1 && 216 !_tolerance.less(0, _data[_data[p].left].dmin)) {216 !_tolerance.less(0, _data[_data[p].left].dmin)) { 217 217 p = _data[p].left; 218 218 } … … 231 231 } 232 232 233 void addPathCost(int p, Value x) {233 void addPathCost(int p, Value x) { 234 234 if (!_tolerance.less(x, _max_value)) { 235 _data[p].dmin = x;_data[p].dcost = x; 235 _data[p].dmin = x; 236 _data[p].dcost = x; 236 237 } else if (!_tolerance.less(x, _max_value)) { 237 238 _data[p].dmin = 0; … … 364 365 Value aa = _data[a].dcost; 365 366 if (_tolerance.less(aa, _max_value)) { 366 aa += min;367 aa += min; 367 368 } 368 369 … … 372 373 Value bb = _data[b].dcost; 373 374 if (_tolerance.less(bb, _max_value)) { 374 bb += ab;375 bb += ab; 375 376 } 376 377 … … 381 382 cc = _data[c].dmin; 382 383 if (_tolerance.less(cc, _max_value)) { 383 cc +=min;384 cc += min; 384 385 } 385 386 } … … 687 688 } 688 689 689 int findPath(int v) {690 int findPath(int v) { 690 691 splay(v); 691 692 return v; 692 693 } 693 694 694 int findPathCost(int p, Value &d) {695 int findPathCost(int p, Value &d) { 695 696 while ((_data[p].right != 1 && 696 697 !_tolerance.less(0, _data[_data[p].right].dmin))  … … 709 710 } 710 711 711 int findTail(int p) {712 int findTail(int p) { 712 713 while (_data[p].right != 1) { 713 714 p = _data[p].right; … … 717 718 } 718 719 719 void addPathCost(int p, Value x) {720 void addPathCost(int p, Value x) { 720 721 if (!_tolerance.less(x, _max_value)) { 721 722 _data[p].dmin = x;_data[p].dcost = x; … … 756 757 _data[p].dmin = min; 757 758 } 758 if (q !=1){759 if (q != 1){ 759 760 _data[q].parent = v; 760 761 if (_tolerance.less(_data[q].dmin,_max_value)) { … … 764 765 _data[v].left = p; 765 766 _data[v].right = q; 766 if (_tolerance.less(min, _max_value)) {767 if (_tolerance.less(min, _max_value)) { 767 768 _data[v].dcost = _data[v].dmin  min; 768 769 }
Note: See TracChangeset
for help on using the changeset viewer.