3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
18 #ifndef LEMON_DYNAMIC_TREE_H
19 #define LEMON_DYNAMIC_TREE_H
23 /// \brief The dynamic tree data structure of Sleator and Tarjan.
28 #include <lemon/tolerance.h>
34 /// \brief The dynamic tree data structure of Sleator and Tarjan.
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.
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
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.
56 /// \author Hamori Tamas
58 template <typename _Value, typename _ItemIntMap,
59 typename _Tolerance, bool _enableSize>
61 template <typename _Value, typename _ItemIntMap,
62 typename _Tolerance = lemon::Tolerance<_Value>,
63 bool _enableSize = true>
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.
73 /// \brief The tolerance used by the algorithm.
74 typedef _Tolerance Tolerance;
80 std::vector<ItemData> _data;
86 /// \brief The constructor of the class.
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) {}
96 /// \brief Clears the data structure
98 /// Clears the data structure
103 /// \brief Sets the tolerance used by algorithm.
105 /// Sets the tolerance used by algorithm.
106 void tolerance(const Tolerance& tolerance) const {
107 _tolerance = tolerance;
111 /// \brief Returns the tolerance used by algorithm.
113 /// Returns the tolerance used by algorithm.
114 const Tolerance& tolerance() const {
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;
123 /// \brief Return the root of the tree containing node with itemtype
125 Item findRoot(const Item &item) {
126 return _data[findTail(expose(_iim[item]))].id;
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;
135 /// \brief Return the minimum cost containing node.
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;
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);
150 /// \brief Combine the trees containing nodes \e item1 and \e item2
151 /// by adding an edge from \e item1 \e item2.
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){
159 join(-1, expose(v), p);
160 _data[v].successor = -1;
161 _data[v].size += _data[p].size;
165 /// \brief Divide the tree containing node \e item into two trees by
166 /// deleting the edge out of \e item.
168 /// This operation assumes that \e item is not a tree root.
169 void cut(const Item &item) {
175 _data[p].successor = v;
177 _data[v].size -= _data[q].size;
179 _data[q].successor = _data[v].successor;
181 _data[v].successor = -1;
185 Item parent(const Item &item){
186 return _data[_iim[item].p].id;
189 ///\brief Return the upper bound of the costs.
190 Value maxValue() const {
196 int makePath(const Item &item) {
197 _iim.set(item, _data.size());
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)) {
215 } else if (_data[p].left != -1 &&
216 !_tolerance.less(0, _data[_data[p].left].dmin)){
226 while (_data[p].right != -1) {
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)) {
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;
250 pmin = _data[p].dmin;
253 qmin = _data[q].dmin;
256 if (_tolerance.less(vmin, qmin)) {
257 if (_tolerance.less(vmin,pmin)) {
262 } else if (_tolerance.less(qmin,pmin)) {
270 _data[p].dmin -= min;
274 if (_tolerance.less(_data[q].dmin,_max_value)) {
275 _data[q].dmin -= min;
280 if (_tolerance.less(min,_max_value)) {
281 _data[v].dcost = _data[v].dmin - min;
286 void split(int &p, int v, int &q){
289 if (_data[v].left != -1){
291 _data[p].dmin += _data[v].dmin;
292 _data[p].parent = -1;
296 if (_data[v].right != -1) {
298 if (_tolerance.less(_data[q].dmin, _max_value)) {
299 _data[q].dmin += _data[v].dmin;
301 _data[q].parent = -1;
304 if (_tolerance.less(_data[v].dcost, _max_value)) {
305 _data[v].dmin += _data[v].dcost;
308 _data[v].dmin = _data[v].dcost;
316 w = _data[findPath(v)].successor;
319 _data[q].successor = v;
325 _data[p].successor = -1;
330 while (_data[v].parent != -1) {
331 if (v == _data[_data[v].parent].left) {
332 if (_data[_data[v].parent].parent == -1) {
335 if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
336 zig(_data[v].parent);
344 if (_data[_data[v].parent].parent == -1) {
347 if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
351 zag(_data[v].parent);
361 Value min = _data[_data[v].parent].dmin;
362 int a = _data[v].parent;
364 Value aa = _data[a].dcost;
365 if (_tolerance.less(aa, _max_value)) {
371 Value ab = min + _data[b].dmin;
372 Value bb = _data[b].dcost;
373 if (_tolerance.less(bb, _max_value)) {
378 Value cc = _max_value;
379 if (_data[a].right != -1) {
382 if (_tolerance.less(cc, _max_value)) {
388 Value dd = _max_value;
389 if (_data[v].left != -1){
391 dd = ab + _data[d].dmin;
395 Value ee = _max_value;
396 if (_data[v].right != -1) {
398 ee = ab + _data[e].dmin;
402 if (_tolerance.less(0, _data[b].dmin) ||
403 (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
406 if (_tolerance.less(aa, cc)) {
407 if (_tolerance.less(aa, ee)) {
412 } else if (_tolerance.less(cc, ee)) {
420 if (_tolerance.less(aa, _max_value)) {
421 _data[a].dcost -= min2;
423 _data[a].dmin = min2;
424 if (_tolerance.less(min2,_max_value)) {
425 _data[a].dmin -= min;
427 _data[a].size -= _data[b].size;
429 if (_tolerance.less(bb, _max_value)) {
430 _data[b].dcost -= min;
433 _data[b].size += _data[a].size;
436 if (_tolerance.less(cc, _max_value)) {
437 _data[c].dmin -= min2;
441 _data[d].dmin = dd - min;
442 _data[a].size += _data[d].size;
443 _data[b].size -= _data[d].size;
446 _data[e].dmin = ee - min2;
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;
454 _data[w].left = _data[v].right;
456 if (_data[v].parent != -1){
457 if (_data[_data[v].parent].right == w) {
458 _data[_data[v].parent].right = v;
460 _data[_data[v].parent].left = v;
463 if (_data[w].left != -1){
464 _data[_data[w].left].parent = w;
471 Value min = _data[_data[v].parent].dmin;
473 int a = _data[v].parent;
474 Value aa = _data[a].dcost;
475 if (_tolerance.less(aa, _max_value)) {
480 Value ab = min + _data[b].dmin;
481 Value bb = _data[b].dcost;
482 if (_tolerance.less(bb, _max_value)) {
487 Value cc = _max_value;
488 if (_data[a].left != -1){
490 cc = min + _data[c].dmin;
494 Value dd = _max_value;
495 if (_data[v].right!=-1) {
498 if (_tolerance.less(dd, _max_value)) {
504 Value ee = _max_value;
505 if (_data[v].left != -1){
507 ee = ab + _data[e].dmin;
511 if (_tolerance.less(0, _data[b].dmin) ||
512 (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
515 if (_tolerance.less(aa, cc)) {
516 if (_tolerance.less(aa, ee)) {
521 } else if (_tolerance.less(cc, ee)) {
528 if (_tolerance.less(aa, _max_value)) {
529 _data[a].dcost -= min2;
531 _data[a].dmin = min2;
532 if (_tolerance.less(min2, _max_value)) {
533 _data[a].dmin -= min;
535 _data[a].size -= _data[b].size;
537 if (_tolerance.less(bb, _max_value)) {
538 _data[b].dcost -= min;
541 _data[b].size += _data[a].size;
543 _data[c].dmin = cc - min2;
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;
554 _data[e].dmin = ee - min2;
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;
562 _data[w].right = _data[v].left;
564 if (_data[v].parent != -1){
565 if (_data[_data[v].parent].left == w) {
566 _data[_data[v].parent].left = v;
568 _data[_data[v].parent].right = v;
571 if (_data[w].right != -1){
572 _data[_data[w].right].parent = w;
590 ItemData(const Item &item)
591 : id(item), size(1), successor(), parent(-1),
592 left(-1), right(-1), dmin(0), dcost(0) {}
597 template <typename _Value, typename _ItemIntMap, typename _Tolerance>
598 class DynamicTree<_Value, _ItemIntMap, _Tolerance, false> {
600 typedef _ItemIntMap ItemIntMap;
601 typedef typename ItemIntMap::Key Item;
602 typedef _Value Value;
603 typedef _Tolerance Tolerance;
609 std::vector<ItemData> _data;
612 Tolerance _tolerance;
615 DynamicTree(ItemIntMap &iim, const Tolerance& tolerance = Tolerance())
616 : _iim(iim), _max_value(std::numeric_limits<Value>::max()),
617 _tolerance(tolerance) {}
625 void tolerance(const Tolerance& tolerance) const {
626 _tolerance = tolerance;
630 const Tolerance& tolerance() const {
634 void makeTree(const Item &item) {
635 _data[makePath(item)].successor = -1;
638 Item findRoot(const Item &item) {
639 return _data[findTail(expose(_iim[item]))].id;
642 Item findCost(const Item &item, Value& d){
643 return _data[findPathCost(expose(_iim[item]),d)].id;
646 void addCost(const Item &item, Value x){
647 addPathCost(expose(_iim[item]), x);
650 void link(const Item &item1, const Item &item2){
654 join(-1, expose(v), p);
655 _data[v].successor = -1;
658 void cut(const Item &item) {
664 _data[p].successor = v;
667 _data[q].successor = _data[v].successor;
669 _data[v].successor = -1;
672 Item parent(const Item &item){
673 return _data[_iim[item].p].id;
676 Value maxValue() const {
682 int makePath(const Item &item) {
683 _iim.set(item, _data.size());
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)) {
701 } else if (_data[p].left != -1 &&
702 !_tolerance.less(0, _data[_data[p].left].dmin)){
712 while (_data[p].right != -1) {
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)) {
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;
736 pmin = _data[p].dmin;
739 qmin = _data[q].dmin;
742 if (_tolerance.less(vmin, qmin)) {
743 if (_tolerance.less(vmin,pmin)) {
748 } else if (_tolerance.less(qmin,pmin)) {
756 _data[p].dmin -= min;
760 if (_tolerance.less(_data[q].dmin,_max_value)) {
761 _data[q].dmin -= min;
766 if (_tolerance.less(min,_max_value)) {
767 _data[v].dcost = _data[v].dmin - min;
772 void split(int &p, int v, int &q){
775 if (_data[v].left != -1){
777 _data[p].dmin += _data[v].dmin;
778 _data[p].parent = -1;
782 if (_data[v].right != -1) {
784 if (_tolerance.less(_data[q].dmin, _max_value)) {
785 _data[q].dmin += _data[v].dmin;
787 _data[q].parent = -1;
790 if (_tolerance.less(_data[v].dcost, _max_value)) {
791 _data[v].dmin += _data[v].dcost;
794 _data[v].dmin = _data[v].dcost;
802 w = _data[findPath(v)].successor;
805 _data[q].successor = v;
811 _data[p].successor = -1;
816 while (_data[v].parent != -1) {
817 if (v == _data[_data[v].parent].left) {
818 if (_data[_data[v].parent].parent == -1) {
821 if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
822 zig(_data[v].parent);
830 if (_data[_data[v].parent].parent == -1) {
833 if (_data[v].parent == _data[_data[_data[v].parent].parent].left) {
837 zag(_data[v].parent);
847 Value min = _data[_data[v].parent].dmin;
848 int a = _data[v].parent;
850 Value aa = _data[a].dcost;
851 if (_tolerance.less(aa, _max_value)) {
857 Value ab = min + _data[b].dmin;
858 Value bb = _data[b].dcost;
859 if (_tolerance.less(bb, _max_value)) {
864 Value cc = _max_value;
865 if (_data[a].right != -1) {
868 if (_tolerance.less(cc, _max_value)) {
874 Value dd = _max_value;
875 if (_data[v].left != -1){
877 dd = ab + _data[d].dmin;
881 Value ee = _max_value;
882 if (_data[v].right != -1) {
884 ee = ab + _data[e].dmin;
888 if (_tolerance.less(0, _data[b].dmin) ||
889 (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
892 if (_tolerance.less(aa, cc)) {
893 if (_tolerance.less(aa, ee)) {
898 } else if (_tolerance.less(cc, ee)) {
906 if (_tolerance.less(aa, _max_value)) {
907 _data[a].dcost -= min2;
909 _data[a].dmin = min2;
910 if (_tolerance.less(min2,_max_value)) {
911 _data[a].dmin -= min;
914 if (_tolerance.less(bb, _max_value)) {
915 _data[b].dcost -= min;
920 if (_tolerance.less(cc, _max_value)) {
921 _data[c].dmin -= min2;
925 _data[d].dmin = dd - min;
928 _data[e].dmin = ee - min2;
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;
936 _data[w].left = _data[v].right;
938 if (_data[v].parent != -1){
939 if (_data[_data[v].parent].right == w) {
940 _data[_data[v].parent].right = v;
942 _data[_data[v].parent].left = v;
945 if (_data[w].left != -1){
946 _data[_data[w].left].parent = w;
953 Value min = _data[_data[v].parent].dmin;
955 int a = _data[v].parent;
956 Value aa = _data[a].dcost;
957 if (_tolerance.less(aa, _max_value)) {
962 Value ab = min + _data[b].dmin;
963 Value bb = _data[b].dcost;
964 if (_tolerance.less(bb, _max_value)) {
969 Value cc = _max_value;
970 if (_data[a].left != -1){
972 cc = min + _data[c].dmin;
976 Value dd = _max_value;
977 if (_data[v].right!=-1) {
980 if (_tolerance.less(dd, _max_value)) {
986 Value ee = _max_value;
987 if (_data[v].left != -1){
989 ee = ab + _data[e].dmin;
993 if (_tolerance.less(0, _data[b].dmin) ||
994 (e != -1 && !_tolerance.less(0, _data[e].dmin))) {
997 if (_tolerance.less(aa, cc)) {
998 if (_tolerance.less(aa, ee)) {
1003 } else if (_tolerance.less(cc, ee)) {
1009 _data[a].dcost = aa;
1010 if (_tolerance.less(aa, _max_value)) {
1011 _data[a].dcost -= min2;
1013 _data[a].dmin = min2;
1014 if (_tolerance.less(min2, _max_value)) {
1015 _data[a].dmin -= min;
1017 _data[b].dcost = bb;
1018 if (_tolerance.less(bb, _max_value)) {
1019 _data[b].dcost -= min;
1021 _data[b].dmin = min;
1023 _data[c].dmin = cc - min2;
1027 if (_tolerance.less(dd, _max_value)) {
1028 _data[d].dmin -= min;
1032 _data[e].dmin = ee - min2;
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;
1042 if (_data[v].parent != -1){
1043 if (_data[_data[v].parent].left == w) {
1044 _data[_data[v].parent].left = v;
1046 _data[_data[v].parent].right = v;
1049 if (_data[w].right != -1){
1050 _data[_data[w].right].parent = w;
1067 ItemData(const Item &item)
1068 : id(item), successor(), parent(-1),
1069 left(-1), right(-1), dmin(0), dcost(0) {}