COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/dynamic_tree.h @ 2514:57143c09dc20

Last change on this file since 2514:57143c09dc20 was 2514:57143c09dc20, checked in by Balazs Dezso, 12 years ago

Redesign the maximum flow algorithms

Redesigned interface
Preflow changed to use elevator
Edmonds-Karp does not use the ResGraphAdaptor?
Goldberg-Tarjan algorithm (Preflow with Dynamic Trees)
Dinitz-Sleator-Tarjan (Blocking flow with Dynamic Tree)

File size: 24.3 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18#ifndef LEMON_DYNAMIC_TREE_H
19#define LEMON_DYNAMIC_TREE_H
20
21/// \ingroup auxdata
22/// \file
23/// \brief The dynamic tree data structure of Sleator and Tarjan.
24///
25
26#include <vector>
27#include <limits>
28#include <lemon/tolerance.h>
29
30namespace lemon {
31
32  /// \ingroup auxdata
33  ///
34  /// \brief The dynamic tree data structure of Sleator and Tarjan.
35  ///
36  /// This class provides an implementation of the dynamic tree data
37  /// structure for maintaining a set of node-disjoint rooted
38  /// trees. Each item has an associated value, and the item with
39  /// minimum value can be find in \f$O(\log(n)\f$ on the path from a
40  /// node to the its root, and the items on such path can be
41  /// increased or decreased globally with a certain value in the same
42  /// running time. We regard a tree edge as directed toward the root,
43  /// that is from child to parent. Its structure can be modified by
44  /// two basic operations: \e link(v,w) adds an edge between a root v
45  /// and a node w in a different component; \e cut(v) removes the
46  /// edge between v and its parent.
47  ///
48  /// \param _Value The value type of the items. 
49  /// \param _ItemIntMap Converts item type of node to integer.
50  /// \param _Tolerance The tolerance class to handle computation
51  /// problems.
52  /// \param _enableSize If true then the data structre manatain the
53  /// size of each tree. The feature is used in \ref GoldbergTarjan
54  /// algorithm. The default value is true.
55  ///
56  /// \author Hamori Tamas
57#ifdef DOXYGEN
58  template <typename _Value, typename _ItemIntMap,
59            typename _Tolerance, bool _enableSize>
60#else
61  template <typename _Value, typename _ItemIntMap,
62            typename _Tolerance = lemon::Tolerance<_Value>,
63            bool _enableSize = true>
64#endif
65  class DynamicTree {
66  public:
67    /// \brief The integer map on the items.
68    typedef _ItemIntMap ItemIntMap;
69    /// \brief The item type of nodes.
70    typedef typename ItemIntMap::Key Item;
71    /// \brief The value type of the algorithms.
72    typedef _Value Value;
73    /// \brief The tolerance used by the algorithm.
74    typedef _Tolerance Tolerance;
75
76  private:
77 
78    class ItemData;
79
80    std::vector<ItemData> _data;
81    ItemIntMap &_iim;
82    Value _max_value;
83    Tolerance _tolerance;
84
85  public:
86    /// \brief The constructor of the class.
87    ///
88    /// \param iim The integer map on the items.
89    /// \param tolerance Tolerance class.
90    DynamicTree(ItemIntMap &iim, const Tolerance& tolerance = Tolerance())
91      : _iim(iim), _max_value(std::numeric_limits<Value>::max()),
92        _tolerance(tolerance) {}
93 
94    ~DynamicTree() {}
95
96    /// \brief Clears the data structure
97    ///
98    /// Clears the data structure
99    void clear() {
100      _data.clear();
101    }
102
103    /// \brief Sets the tolerance used by algorithm.
104    ///
105    /// Sets the tolerance used by algorithm.
106    void tolerance(const Tolerance& tolerance) const {
107      _tolerance = tolerance;
108      return *this;
109    }
110 
111    /// \brief Returns the tolerance used by algorithm.
112    ///
113    /// Returns the tolerance used by algorithm.
114    const Tolerance& tolerance() const {
115      return tolerance;
116    }
117 
118    /// \brief Create a new tree containing a single node with cost zero.
119    void makeTree(const Item &item) {
120      _data[makePath(item)].successor = -1;
121    }
122   
123    /// \brief Return the root of the tree containing node with itemtype
124    /// \e item.
125    Item findRoot(const Item &item) {
126      return _data[findTail(expose(_iim[item]))].id;
127    }
128   
129    /// \brief Return the the value of nodes in the tree containing
130    /// node with itemtype \e item.
131    int findSize(const Item &item) {
132      return _data[expose(_iim[item])].size;
133    }
134   
135    /// \brief Return the minimum cost containing node.
136    ///
137    /// Return into \e d the minimum cost on the tree path from \e item
138    /// to findRoot(item).  Return the last item (closest to its root)
139    /// on this path of the minimum cost.
140    Item findCost(const Item &item, Value& d){
141      return _data[findPathCost(expose(_iim[item]),d)].id;
142    }
143   
144    /// \brief Add \e x value to the cost of every node on the path from
145    /// \e item to findRoot(item).
146    void addCost(const Item &item, Value x){
147      addPathCost(expose(_iim[item]), x);
148    }
149   
150    /// \brief Combine the trees containing nodes \e item1 and \e item2
151    /// by adding an edge from \e item1 \e item2.
152    ///
153    /// This operation assumes that \e item1 is root and \e item2 is in
154    /// a different tree.
155    void link(const Item &item1, const Item &item2){
156      int v = _iim[item1];
157      int w = _iim[item2];
158      int p = expose(w);
159      join(-1, expose(v), p);
160      _data[v].successor = -1;
161      _data[v].size += _data[p].size;
162
163    }   
164   
165    /// \brief Divide the tree containing node \e item into two trees by
166    /// deleting the edge out of \e item.
167    ///
168    /// This operation assumes that \e item is not a tree root.
169    void cut(const Item &item) {
170      int v = _iim[item];
171      int p, q;
172      expose(v);
173      split(p, v, q);
174      if (p != -1) {
175        _data[p].successor = v;
176      }
177      _data[v].size -= _data[q].size;
178      if (q != -1) {
179        _data[q].successor = _data[v].successor;
180      }
181      _data[v].successor = -1;
182    }
183
184    ///\brief
185    Item parent(const Item &item){
186      return _data[_iim[item].p].id;
187    }
188
189    ///\brief Return the upper bound of the costs.
190    Value maxValue() const {
191      return _max_value;
192    }
193   
194  private:
195
196    int makePath(const Item &item) {
197      _iim.set(item, _data.size());
198      ItemData v(item);
199      _data.push_back(v);
200      return _iim[item];
201    }
202
203    int findPath(int v){
204      splay(v);
205      return v;
206    }
207   
208    int findPathCost(int p, Value &d){
209      while ((_data[p].right != -1 &&
210              !_tolerance.less(0, _data[_data[p].right].dmin)) ||
211             (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
212        if (_data[p].right != -1 &&
213            !_tolerance.less(0, _data[_data[p].right].dmin)) {
214          p = _data[p].right;
215        } else if (_data[p].left != -1 &&
216                   !_tolerance.less(0, _data[_data[p].left].dmin)){
217          p = _data[p].left;
218        }
219      }
220      splay(p);
221      d = _data[p].dmin;
222      return p;
223    }
224
225    int findTail(int p){
226      while (_data[p].right != -1) {
227        p = _data[p].right;
228      }
229      splay(p);
230      return p;
231    }
232   
233    void addPathCost(int p, Value x){
234      if (!_tolerance.less(x, _max_value)) {
235        _data[p].dmin = x;_data[p].dcost = x;
236      } else if (!_tolerance.less(-x, _max_value)) {
237        _data[p].dmin = 0;
238        _data[p].dcost = 0;
239      } else {
240        _data[p].dmin += x;
241      }
242    }
243
244    void join(int p, int v, int q) {
245      Value min = _max_value;
246      Value pmin = _max_value;
247      Value vmin = _data[v].dmin;
248      Value qmin = _max_value;
249      if (p != -1){
250        pmin = _data[p].dmin;
251      }
252      if (q != -1){
253        qmin = _data[q].dmin;
254      }
255       
256      if (_tolerance.less(vmin, qmin)) {
257        if (_tolerance.less(vmin,pmin)) {
258          min = vmin;
259        } else {
260          min = pmin;
261        }
262      } else if (_tolerance.less(qmin,pmin)) {
263        min = qmin;
264      } else {
265        min = pmin;
266      }
267
268      if (p != -1){
269        _data[p].parent = v;
270        _data[p].dmin -= min;
271      }
272      if (q!=-1){
273        _data[q].parent = v;
274        if (_tolerance.less(_data[q].dmin,_max_value)) {
275          _data[q].dmin -= min;
276        }
277      }
278      _data[v].left = p;
279      _data[v].right = q;
280      if (_tolerance.less(min,_max_value)) {
281        _data[v].dcost = _data[v].dmin - min;
282      }
283      _data[v].dmin = min;
284    }
285
286    void split(int &p, int v, int &q){
287      splay(v);
288      p = -1;
289      if (_data[v].left != -1){
290        p = _data[v].left;
291        _data[p].dmin += _data[v].dmin;
292        _data[p].parent = -1;
293        _data[v].left = -1;
294      }
295      q = -1;
296      if (_data[v].right != -1) {
297        q=_data[v].right;
298        if (_tolerance.less(_data[q].dmin, _max_value)) {
299          _data[q].dmin += _data[v].dmin;
300        }
301        _data[q].parent = -1;
302        _data[v].right = -1;
303      }
304      if (_tolerance.less(_data[v].dcost, _max_value)) {
305        _data[v].dmin += _data[v].dcost;
306        _data[v].dcost = 0;
307      } else {
308        _data[v].dmin = _data[v].dcost;
309      }
310    }
311 
312    int expose(int v) {
313      int p, q, r, w;
314      p = -1;
315      while (v != -1) {
316        w = _data[findPath(v)].successor;
317        split(q, v, r);
318        if (q != -1) {
319          _data[q].successor = v;
320        }
321        join(p, v, r);
322        p = v;
323        v = w;
324      }
325      _data[p].successor = -1;
326      return p;
327    }
328
329    void splay(int v) {
330      while (_data[v].parent != -1) {
331        if (v == _data[_data[v].parent].left) {
332          if (_data[_data[v].parent].parent == -1) {
333            zig(v);
334          } else {
335            if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
336              zig(_data[v].parent);
337              zig(v);
338            } else {
339              zig(v);
340              zag(v);
341            }
342          }
343        } else {
344          if (_data[_data[v].parent].parent == -1) {
345            zag(v);
346          } else {
347            if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
348              zag(v);
349              zig(v);
350            } else {
351              zag(_data[v].parent);
352              zag(v);
353            }
354          }
355        }
356      }
357    }
358
359
360    void zig(int v) {
361      Value min = _data[_data[v].parent].dmin;
362      int a = _data[v].parent;
363       
364      Value aa = _data[a].dcost;
365      if (_tolerance.less(aa, _max_value)) {
366        aa+= min;
367      }
368
369
370      int b = v;
371      Value ab = min + _data[b].dmin;
372      Value bb = _data[b].dcost;
373      if (_tolerance.less(bb, _max_value)) {
374        bb+= ab;
375      }
376
377      int c = -1;
378      Value cc = _max_value;
379      if (_data[a].right != -1) {
380        c = _data[a].right;
381        cc = _data[c].dmin;
382        if (_tolerance.less(cc, _max_value)) {
383          cc+=min;
384        }
385      }
386
387      int d = -1;
388      Value dd = _max_value;
389      if (_data[v].left != -1){
390        d = _data[v].left;
391        dd = ab + _data[d].dmin;
392      }
393
394      int e = -1;
395      Value ee = _max_value;
396      if (_data[v].right != -1) {
397        e = _data[v].right;
398        ee = ab + _data[e].dmin;
399      }
400
401      Value min2;
402      if (_tolerance.less(0, _data[b].dmin) ||
403          (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
404        min2 = min;
405      } else {
406        if (_tolerance.less(aa, cc)) {
407          if (_tolerance.less(aa, ee)) {
408            min2 = aa;
409          } else {
410            min2 = ee;
411          }
412        } else if (_tolerance.less(cc, ee)) {
413          min2 = cc;
414        } else {
415          min2 = ee;
416        }
417      }
418       
419      _data[a].dcost = aa;
420      if (_tolerance.less(aa, _max_value)) {
421        _data[a].dcost -= min2;
422      }
423      _data[a].dmin = min2;
424      if (_tolerance.less(min2,_max_value)) {
425        _data[a].dmin -= min;
426      }
427      _data[a].size -= _data[b].size;
428      _data[b].dcost = bb;
429      if (_tolerance.less(bb, _max_value)) {
430        _data[b].dcost -= min;
431      }
432      _data[b].dmin = min;
433      _data[b].size += _data[a].size;
434      if (c != -1) {
435        _data[c].dmin = cc;
436        if (_tolerance.less(cc, _max_value)) {
437          _data[c].dmin -= min2;
438        }
439      }
440      if (d != -1) {
441        _data[d].dmin = dd - min;
442        _data[a].size += _data[d].size;
443        _data[b].size -= _data[d].size;
444      }
445      if (e != -1) {
446        _data[e].dmin = ee - min2;
447      }
448       
449      int w = _data[v].parent;
450      _data[v].successor = _data[w].successor;
451      _data[w].successor = -1;
452      _data[v].parent = _data[w].parent;
453      _data[w].parent = v;
454      _data[w].left = _data[v].right;
455      _data[v].right = w;
456      if (_data[v].parent != -1){
457        if (_data[_data[v].parent].right == w) {
458          _data[_data[v].parent].right = v;
459        } else {
460          _data[_data[v].parent].left = v;
461        }
462      }
463      if (_data[w].left != -1){
464        _data[_data[w].left].parent = w;
465      }
466    }
467
468
469    void zag(int v) {
470
471      Value min = _data[_data[v].parent].dmin;
472
473      int a = _data[v].parent;
474      Value aa = _data[a].dcost;
475      if (_tolerance.less(aa, _max_value)) {
476        aa += min;
477      }
478       
479      int b = v;
480      Value ab = min + _data[b].dmin;
481      Value bb = _data[b].dcost;
482      if (_tolerance.less(bb, _max_value)) {
483        bb += ab;
484      }
485
486      int c = -1;
487      Value cc = _max_value;
488      if (_data[a].left != -1){
489        c = _data[a].left;
490        cc = min + _data[c].dmin;
491      }
492
493      int d = -1;
494      Value dd = _max_value;
495      if (_data[v].right!=-1) {
496        d = _data[v].right;
497        dd = _data[d].dmin;
498        if (_tolerance.less(dd, _max_value)) {
499          dd += ab;
500        }
501      }
502
503      int e = -1;
504      Value ee = _max_value;
505      if (_data[v].left != -1){
506        e = _data[v].left;
507        ee = ab + _data[e].dmin;
508      }
509
510      Value min2;
511      if (_tolerance.less(0, _data[b].dmin) ||
512          (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
513        min2 = min;
514      } else {
515        if (_tolerance.less(aa, cc)) {
516          if (_tolerance.less(aa, ee)) {
517            min2 = aa;
518          } else {
519            min2 = ee;
520          }
521        } else if (_tolerance.less(cc, ee)) {
522          min2 = cc;
523        } else {
524          min2 = ee;
525        }
526      }
527      _data[a].dcost = aa;
528      if (_tolerance.less(aa, _max_value)) {
529        _data[a].dcost -= min2;
530      }
531      _data[a].dmin = min2;
532      if (_tolerance.less(min2, _max_value)) {
533        _data[a].dmin -= min;
534      }
535      _data[a].size -= _data[b].size;
536      _data[b].dcost = bb;
537      if (_tolerance.less(bb, _max_value)) {
538        _data[b].dcost -= min;
539      }
540      _data[b].dmin = min;
541      _data[b].size += _data[a].size;
542      if (c != -1) {
543        _data[c].dmin = cc - min2;
544      }
545      if (d != -1) {
546        _data[d].dmin = dd;
547        _data[a].size += _data[d].size;
548        _data[b].size -= _data[d].size;
549        if (_tolerance.less(dd, _max_value)) {
550          _data[d].dmin -= min;
551        }
552      }
553      if (e != -1) {
554        _data[e].dmin = ee - min2;
555      }
556       
557      int w = _data[v].parent;
558      _data[v].successor = _data[w].successor;
559      _data[w].successor = -1;
560      _data[v].parent = _data[w].parent;
561      _data[w].parent = v;
562      _data[w].right = _data[v].left;
563      _data[v].left = w;
564      if (_data[v].parent != -1){
565        if (_data[_data[v].parent].left == w) {
566          _data[_data[v].parent].left = v;
567        } else {
568          _data[_data[v].parent].right = v;
569        }
570      }
571      if (_data[w].right != -1){
572        _data[_data[w].right].parent = w;
573      }
574    }
575
576  private:
577
578    class ItemData {
579    public:
580      Item id;
581      int size;
582      int successor;
583      int parent;
584      int left;
585      int right;
586      Value dmin;
587      Value dcost;
588       
589    public:
590      ItemData(const Item &item)
591        : id(item), size(1), successor(), parent(-1),
592          left(-1), right(-1), dmin(0), dcost(0) {}
593    };
594     
595  };
596
597  template <typename _Value, typename _ItemIntMap, typename _Tolerance>
598  class DynamicTree<_Value, _ItemIntMap, _Tolerance, false> {
599  public:
600    typedef _ItemIntMap ItemIntMap;
601    typedef typename ItemIntMap::Key Item;
602    typedef _Value Value;
603    typedef _Tolerance Tolerance;
604
605  private:
606 
607    class ItemData;
608
609    std::vector<ItemData> _data;
610    ItemIntMap &_iim;
611    Value _max_value;
612    Tolerance _tolerance;
613
614  public:
615    DynamicTree(ItemIntMap &iim, const Tolerance& tolerance = Tolerance())
616      : _iim(iim), _max_value(std::numeric_limits<Value>::max()),
617        _tolerance(tolerance) {}
618 
619    ~DynamicTree() {}
620
621    void clear() {
622      _data.clear();
623    }
624
625    void tolerance(const Tolerance& tolerance) const {
626      _tolerance = tolerance;
627      return *this;
628    }
629 
630    const Tolerance& tolerance() const {
631      return tolerance;
632    }
633 
634    void makeTree(const Item &item) {
635      _data[makePath(item)].successor = -1;
636    }
637   
638    Item findRoot(const Item &item) {
639      return _data[findTail(expose(_iim[item]))].id;
640    }
641   
642    Item findCost(const Item &item, Value& d){
643      return _data[findPathCost(expose(_iim[item]),d)].id;
644    }
645   
646    void addCost(const Item &item, Value x){
647      addPathCost(expose(_iim[item]), x);
648    }
649   
650    void link(const Item &item1, const Item &item2){
651      int v = _iim[item1];
652      int w = _iim[item2];
653      int p = expose(w);
654      join(-1, expose(v), p);
655      _data[v].successor = -1;
656    }   
657   
658    void cut(const Item &item) {
659      int v = _iim[item];
660      int p, q;
661      expose(v);
662      split(p, v, q);
663      if (p != -1) {
664        _data[p].successor = v;
665      }
666      if (q != -1) {
667        _data[q].successor = _data[v].successor;
668      }
669      _data[v].successor = -1;
670    }
671
672    Item parent(const Item &item){
673      return _data[_iim[item].p].id;
674    }
675
676    Value maxValue() const {
677      return _max_value;
678    }
679   
680  private:
681
682    int makePath(const Item &item) {
683      _iim.set(item, _data.size());
684      ItemData v(item);
685      _data.push_back(v);
686      return _iim[item];
687    }
688
689    int findPath(int v){
690      splay(v);
691      return v;
692    }
693   
694    int findPathCost(int p, Value &d){
695      while ((_data[p].right != -1 &&
696              !_tolerance.less(0, _data[_data[p].right].dmin)) ||
697             (_data[p].left != -1 && _tolerance.less(0, _data[p].dcost))) {
698        if (_data[p].right != -1 &&
699            !_tolerance.less(0, _data[_data[p].right].dmin)) {
700          p = _data[p].right;
701        } else if (_data[p].left != -1 &&
702                   !_tolerance.less(0, _data[_data[p].left].dmin)){
703          p = _data[p].left;
704        }
705      }
706      splay(p);
707      d = _data[p].dmin;
708      return p;
709    }
710
711    int findTail(int p){
712      while (_data[p].right != -1) {
713        p = _data[p].right;
714      }
715      splay(p);
716      return p;
717    }
718   
719    void addPathCost(int p, Value x){
720      if (!_tolerance.less(x, _max_value)) {
721        _data[p].dmin = x;_data[p].dcost = x;
722      } else if (!_tolerance.less(-x, _max_value)) {
723        _data[p].dmin = 0;
724        _data[p].dcost = 0;
725      } else {
726        _data[p].dmin += x;
727      }
728    }
729
730    void join(int p, int v, int q) {
731      Value min = _max_value;
732      Value pmin = _max_value;
733      Value vmin = _data[v].dmin;
734      Value qmin = _max_value;
735      if (p != -1){
736        pmin = _data[p].dmin;
737      }
738      if (q != -1){
739        qmin = _data[q].dmin;
740      }
741       
742      if (_tolerance.less(vmin, qmin)) {
743        if (_tolerance.less(vmin,pmin)) {
744          min = vmin;
745        } else {
746          min = pmin;
747        }
748      } else if (_tolerance.less(qmin,pmin)) {
749        min = qmin;
750      } else {
751        min = pmin;
752      }
753
754      if (p != -1){
755        _data[p].parent = v;
756        _data[p].dmin -= min;
757      }
758      if (q!=-1){
759        _data[q].parent = v;
760        if (_tolerance.less(_data[q].dmin,_max_value)) {
761          _data[q].dmin -= min;
762        }
763      }
764      _data[v].left = p;
765      _data[v].right = q;
766      if (_tolerance.less(min,_max_value)) {
767        _data[v].dcost = _data[v].dmin - min;
768      }
769      _data[v].dmin = min;
770    }
771
772    void split(int &p, int v, int &q){
773      splay(v);
774      p = -1;
775      if (_data[v].left != -1){
776        p = _data[v].left;
777        _data[p].dmin += _data[v].dmin;
778        _data[p].parent = -1;
779        _data[v].left = -1;
780      }
781      q = -1;
782      if (_data[v].right != -1) {
783        q=_data[v].right;
784        if (_tolerance.less(_data[q].dmin, _max_value)) {
785          _data[q].dmin += _data[v].dmin;
786        }
787        _data[q].parent = -1;
788        _data[v].right = -1;
789      }
790      if (_tolerance.less(_data[v].dcost, _max_value)) {
791        _data[v].dmin += _data[v].dcost;
792        _data[v].dcost = 0;
793      } else {
794        _data[v].dmin = _data[v].dcost;
795      }
796    }
797 
798    int expose(int v) {
799      int p, q, r, w;
800      p = -1;
801      while (v != -1) {
802        w = _data[findPath(v)].successor;
803        split(q, v, r);
804        if (q != -1) {
805          _data[q].successor = v;
806        }
807        join(p, v, r);
808        p = v;
809        v = w;
810      }
811      _data[p].successor = -1;
812      return p;
813    }
814
815    void splay(int v) {
816      while (_data[v].parent != -1) {
817        if (v == _data[_data[v].parent].left) {
818          if (_data[_data[v].parent].parent == -1) {
819            zig(v);
820          } else {
821            if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
822              zig(_data[v].parent);
823              zig(v);
824            } else {
825              zig(v);
826              zag(v);
827            }
828          }
829        } else {
830          if (_data[_data[v].parent].parent == -1) {
831            zag(v);
832          } else {
833            if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
834              zag(v);
835              zig(v);
836            } else {
837              zag(_data[v].parent);
838              zag(v);
839            }
840          }
841        }
842      }
843    }
844
845
846    void zig(int v) {
847      Value min = _data[_data[v].parent].dmin;
848      int a = _data[v].parent;
849       
850      Value aa = _data[a].dcost;
851      if (_tolerance.less(aa, _max_value)) {
852        aa+= min;
853      }
854
855
856      int b = v;
857      Value ab = min + _data[b].dmin;
858      Value bb = _data[b].dcost;
859      if (_tolerance.less(bb, _max_value)) {
860        bb+= ab;
861      }
862
863      int c = -1;
864      Value cc = _max_value;
865      if (_data[a].right != -1) {
866        c = _data[a].right;
867        cc = _data[c].dmin;
868        if (_tolerance.less(cc, _max_value)) {
869          cc+=min;
870        }
871      }
872
873      int d = -1;
874      Value dd = _max_value;
875      if (_data[v].left != -1){
876        d = _data[v].left;
877        dd = ab + _data[d].dmin;
878      }
879
880      int e = -1;
881      Value ee = _max_value;
882      if (_data[v].right != -1) {
883        e = _data[v].right;
884        ee = ab + _data[e].dmin;
885      }
886
887      Value min2;
888      if (_tolerance.less(0, _data[b].dmin) ||
889          (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
890        min2 = min;
891      } else {
892        if (_tolerance.less(aa, cc)) {
893          if (_tolerance.less(aa, ee)) {
894            min2 = aa;
895          } else {
896            min2 = ee;
897          }
898        } else if (_tolerance.less(cc, ee)) {
899          min2 = cc;
900        } else {
901          min2 = ee;
902        }
903      }
904       
905      _data[a].dcost = aa;
906      if (_tolerance.less(aa, _max_value)) {
907        _data[a].dcost -= min2;
908      }
909      _data[a].dmin = min2;
910      if (_tolerance.less(min2,_max_value)) {
911        _data[a].dmin -= min;
912      }
913      _data[b].dcost = bb;
914      if (_tolerance.less(bb, _max_value)) {
915        _data[b].dcost -= min;
916      }
917      _data[b].dmin = min;
918      if (c != -1) {
919        _data[c].dmin = cc;
920        if (_tolerance.less(cc, _max_value)) {
921          _data[c].dmin -= min2;
922        }
923      }
924      if (d != -1) {
925        _data[d].dmin = dd - min;
926      }
927      if (e != -1) {
928        _data[e].dmin = ee - min2;
929      }
930       
931      int w = _data[v].parent;
932      _data[v].successor = _data[w].successor;
933      _data[w].successor = -1;
934      _data[v].parent = _data[w].parent;
935      _data[w].parent = v;
936      _data[w].left = _data[v].right;
937      _data[v].right = w;
938      if (_data[v].parent != -1){
939        if (_data[_data[v].parent].right == w) {
940          _data[_data[v].parent].right = v;
941        } else {
942          _data[_data[v].parent].left = v;
943        }
944      }
945      if (_data[w].left != -1){
946        _data[_data[w].left].parent = w;
947      }
948    }
949
950
951    void zag(int v) {
952
953      Value min = _data[_data[v].parent].dmin;
954
955      int a = _data[v].parent;
956      Value aa = _data[a].dcost;
957      if (_tolerance.less(aa, _max_value)) {
958        aa += min;
959      }
960       
961      int b = v;
962      Value ab = min + _data[b].dmin;
963      Value bb = _data[b].dcost;
964      if (_tolerance.less(bb, _max_value)) {
965        bb += ab;
966      }
967
968      int c = -1;
969      Value cc = _max_value;
970      if (_data[a].left != -1){
971        c = _data[a].left;
972        cc = min + _data[c].dmin;
973      }
974
975      int d = -1;
976      Value dd = _max_value;
977      if (_data[v].right!=-1) {
978        d = _data[v].right;
979        dd = _data[d].dmin;
980        if (_tolerance.less(dd, _max_value)) {
981          dd += ab;
982        }
983      }
984
985      int e = -1;
986      Value ee = _max_value;
987      if (_data[v].left != -1){
988        e = _data[v].left;
989        ee = ab + _data[e].dmin;
990      }
991
992      Value min2;
993      if (_tolerance.less(0, _data[b].dmin) ||
994          (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
995        min2 = min;
996      } else {
997        if (_tolerance.less(aa, cc)) {
998          if (_tolerance.less(aa, ee)) {
999            min2 = aa;
1000          } else {
1001            min2 = ee;
1002          }
1003        } else if (_tolerance.less(cc, ee)) {
1004          min2 = cc;
1005        } else {
1006          min2 = ee;
1007        }
1008      }
1009      _data[a].dcost = aa;
1010      if (_tolerance.less(aa, _max_value)) {
1011        _data[a].dcost -= min2;
1012      }
1013      _data[a].dmin = min2;
1014      if (_tolerance.less(min2, _max_value)) {
1015        _data[a].dmin -= min;
1016      }
1017      _data[b].dcost = bb;
1018      if (_tolerance.less(bb, _max_value)) {
1019        _data[b].dcost -= min;
1020      }
1021      _data[b].dmin = min;
1022      if (c != -1) {
1023        _data[c].dmin = cc - min2;
1024      }
1025      if (d != -1) {
1026        _data[d].dmin = dd;
1027        if (_tolerance.less(dd, _max_value)) {
1028          _data[d].dmin -= min;
1029        }
1030      }
1031      if (e != -1) {
1032        _data[e].dmin = ee - min2;
1033      }
1034       
1035      int w = _data[v].parent;
1036      _data[v].successor = _data[w].successor;
1037      _data[w].successor = -1;
1038      _data[v].parent = _data[w].parent;
1039      _data[w].parent = v;
1040      _data[w].right = _data[v].left;
1041      _data[v].left = w;
1042      if (_data[v].parent != -1){
1043        if (_data[_data[v].parent].left == w) {
1044          _data[_data[v].parent].left = v;
1045        } else {
1046          _data[_data[v].parent].right = v;
1047        }
1048      }
1049      if (_data[w].right != -1){
1050        _data[_data[w].right].parent = w;
1051      }
1052    }
1053
1054  private:
1055
1056    class ItemData {
1057    public:
1058      Item id;
1059      int successor;
1060      int parent;
1061      int left;
1062      int right;
1063      Value dmin;
1064      Value dcost;
1065       
1066    public:
1067      ItemData(const Item &item)
1068        : id(item), successor(), parent(-1),
1069          left(-1), right(-1), dmin(0), dcost(0) {}
1070    };
1071     
1072  };
1073
1074}
1075
1076#endif
Note: See TracBrowser for help on using the repository browser.