1.1 --- a/lemon/matching.h Sun Mar 07 09:49:42 2010 +0000
1.2 +++ b/lemon/matching.h Wed Mar 17 10:23:17 2010 +0100
1.3 @@ -805,41 +805,60 @@
1.4 if (!_matching) {
1.5 _matching = new MatchingMap(_graph);
1.6 }
1.7 +
1.8 if (!_node_potential) {
1.9 _node_potential = new NodePotential(_graph);
1.10 }
1.11 +
1.12 if (!_blossom_set) {
1.13 _blossom_index = new IntNodeMap(_graph);
1.14 _blossom_set = new BlossomSet(*_blossom_index);
1.15 _blossom_data = new RangeMap<BlossomData>(_blossom_num);
1.16 + } else if (_blossom_data->size() != _blossom_num) {
1.17 + delete _blossom_data;
1.18 + _blossom_data = new RangeMap<BlossomData>(_blossom_num);
1.19 }
1.20
1.21 if (!_node_index) {
1.22 _node_index = new IntNodeMap(_graph);
1.23 _node_heap_index = new IntArcMap(_graph);
1.24 _node_data = new RangeMap<NodeData>(_node_num,
1.25 - NodeData(*_node_heap_index));
1.26 + NodeData(*_node_heap_index));
1.27 + } else {
1.28 + delete _node_data;
1.29 + _node_data = new RangeMap<NodeData>(_node_num,
1.30 + NodeData(*_node_heap_index));
1.31 }
1.32
1.33 if (!_tree_set) {
1.34 _tree_set_index = new IntIntMap(_blossom_num);
1.35 _tree_set = new TreeSet(*_tree_set_index);
1.36 + } else {
1.37 + _tree_set_index->resize(_blossom_num);
1.38 }
1.39 +
1.40 if (!_delta1) {
1.41 _delta1_index = new IntNodeMap(_graph);
1.42 _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index);
1.43 }
1.44 +
1.45 if (!_delta2) {
1.46 _delta2_index = new IntIntMap(_blossom_num);
1.47 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
1.48 + } else {
1.49 + _delta2_index->resize(_blossom_num);
1.50 }
1.51 +
1.52 if (!_delta3) {
1.53 _delta3_index = new IntEdgeMap(_graph);
1.54 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
1.55 }
1.56 +
1.57 if (!_delta4) {
1.58 _delta4_index = new IntIntMap(_blossom_num);
1.59 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
1.60 + } else {
1.61 + _delta4_index->resize(_blossom_num);
1.62 }
1.63 }
1.64
1.65 @@ -1685,6 +1704,9 @@
1.66 void init() {
1.67 createStructures();
1.68
1.69 + _blossom_node_list.clear();
1.70 + _blossom_potential.clear();
1.71 +
1.72 for (ArcIt e(_graph); e != INVALID; ++e) {
1.73 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
1.74 }
1.75 @@ -1698,6 +1720,13 @@
1.76 (*_delta2_index)[i] = _delta2->PRE_HEAP;
1.77 (*_delta4_index)[i] = _delta4->PRE_HEAP;
1.78 }
1.79 +
1.80 + _delta1->clear();
1.81 + _delta2->clear();
1.82 + _delta3->clear();
1.83 + _delta4->clear();
1.84 + _blossom_set->clear();
1.85 + _tree_set->clear();
1.86
1.87 int index = 0;
1.88 for (NodeIt n(_graph); n != INVALID; ++n) {
1.89 @@ -1709,6 +1738,8 @@
1.90 }
1.91 }
1.92 (*_node_index)[n] = index;
1.93 + (*_node_data)[index].heap_index.clear();
1.94 + (*_node_data)[index].heap.clear();
1.95 (*_node_data)[index].pot = max;
1.96 _delta1->push(n, max);
1.97 int blossom =
1.98 @@ -2198,13 +2229,18 @@
1.99 if (!_matching) {
1.100 _matching = new MatchingMap(_graph);
1.101 }
1.102 +
1.103 if (!_node_potential) {
1.104 _node_potential = new NodePotential(_graph);
1.105 }
1.106 +
1.107 if (!_blossom_set) {
1.108 _blossom_index = new IntNodeMap(_graph);
1.109 _blossom_set = new BlossomSet(*_blossom_index);
1.110 _blossom_data = new RangeMap<BlossomData>(_blossom_num);
1.111 + } else if (_blossom_data->size() != _blossom_num) {
1.112 + delete _blossom_data;
1.113 + _blossom_data = new RangeMap<BlossomData>(_blossom_num);
1.114 }
1.115
1.116 if (!_node_index) {
1.117 @@ -2212,23 +2248,36 @@
1.118 _node_heap_index = new IntArcMap(_graph);
1.119 _node_data = new RangeMap<NodeData>(_node_num,
1.120 NodeData(*_node_heap_index));
1.121 + } else if (_node_data->size() != _node_num) {
1.122 + delete _node_data;
1.123 + _node_data = new RangeMap<NodeData>(_node_num,
1.124 + NodeData(*_node_heap_index));
1.125 }
1.126
1.127 if (!_tree_set) {
1.128 _tree_set_index = new IntIntMap(_blossom_num);
1.129 _tree_set = new TreeSet(*_tree_set_index);
1.130 + } else {
1.131 + _tree_set_index->resize(_blossom_num);
1.132 }
1.133 +
1.134 if (!_delta2) {
1.135 _delta2_index = new IntIntMap(_blossom_num);
1.136 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
1.137 + } else {
1.138 + _delta2_index->resize(_blossom_num);
1.139 }
1.140 +
1.141 if (!_delta3) {
1.142 _delta3_index = new IntEdgeMap(_graph);
1.143 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
1.144 }
1.145 +
1.146 if (!_delta4) {
1.147 _delta4_index = new IntIntMap(_blossom_num);
1.148 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
1.149 + } else {
1.150 + _delta4_index->resize(_blossom_num);
1.151 }
1.152 }
1.153
1.154 @@ -2926,6 +2975,9 @@
1.155 void init() {
1.156 createStructures();
1.157
1.158 + _blossom_node_list.clear();
1.159 + _blossom_potential.clear();
1.160 +
1.161 for (ArcIt e(_graph); e != INVALID; ++e) {
1.162 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
1.163 }
1.164 @@ -2937,6 +2989,12 @@
1.165 (*_delta4_index)[i] = _delta4->PRE_HEAP;
1.166 }
1.167
1.168 + _delta2->clear();
1.169 + _delta3->clear();
1.170 + _delta4->clear();
1.171 + _blossom_set->clear();
1.172 + _tree_set->clear();
1.173 +
1.174 int index = 0;
1.175 for (NodeIt n(_graph); n != INVALID; ++n) {
1.176 Value max = - std::numeric_limits<Value>::max();
1.177 @@ -2947,6 +3005,8 @@
1.178 }
1.179 }
1.180 (*_node_index)[n] = index;
1.181 + (*_node_data)[index].heap_index.clear();
1.182 + (*_node_data)[index].heap.clear();
1.183 (*_node_data)[index].pot = max;
1.184 int blossom =
1.185 _blossom_set->insert(n, std::numeric_limits<Value>::max());
2.1 --- a/lemon/unionfind.h Sun Mar 07 09:49:42 2010 +0000
2.2 +++ b/lemon/unionfind.h Wed Mar 17 10:23:17 2010 +0100
2.3 @@ -1288,6 +1288,15 @@
2.4 : index(_index), first_class(-1),
2.5 first_free_class(-1), first_free_node(-1) {}
2.6
2.7 + /// \brief Clears the union-find data structure
2.8 + ///
2.9 + /// Erase each item from the data structure.
2.10 + void clear() {
2.11 + nodes.clear();
2.12 + classes.clear();
2.13 + first_free_node = first_free_class = first_class = -1;
2.14 + }
2.15 +
2.16 /// \brief Insert a new node into a new component.
2.17 ///
2.18 /// Insert a new node into a new component.