1.1 --- a/lemon/matching.h Tue Mar 16 21:27:35 2010 +0100
1.2 +++ b/lemon/matching.h Wed Mar 17 10:29:57 2010 +0100
1.3 @@ -810,41 +810,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 @@ -1588,6 +1607,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 @@ -1601,9 +1623,16 @@
1.76 (*_delta2_index)[i] = _delta2->PRE_HEAP;
1.77 (*_delta4_index)[i] = _delta4->PRE_HEAP;
1.78 }
1.79 -
1.80 +
1.81 _unmatched = _node_num;
1.82
1.83 + _delta1->clear();
1.84 + _delta2->clear();
1.85 + _delta3->clear();
1.86 + _delta4->clear();
1.87 + _blossom_set->clear();
1.88 + _tree_set->clear();
1.89 +
1.90 int index = 0;
1.91 for (NodeIt n(_graph); n != INVALID; ++n) {
1.92 Value max = 0;
1.93 @@ -1614,6 +1643,8 @@
1.94 }
1.95 }
1.96 (*_node_index)[n] = index;
1.97 + (*_node_data)[index].heap_index.clear();
1.98 + (*_node_data)[index].heap.clear();
1.99 (*_node_data)[index].pot = max;
1.100 _delta1->push(n, max);
1.101 int blossom =
1.102 @@ -2237,13 +2268,18 @@
1.103 if (!_matching) {
1.104 _matching = new MatchingMap(_graph);
1.105 }
1.106 +
1.107 if (!_node_potential) {
1.108 _node_potential = new NodePotential(_graph);
1.109 }
1.110 +
1.111 if (!_blossom_set) {
1.112 _blossom_index = new IntNodeMap(_graph);
1.113 _blossom_set = new BlossomSet(*_blossom_index);
1.114 _blossom_data = new RangeMap<BlossomData>(_blossom_num);
1.115 + } else if (_blossom_data->size() != _blossom_num) {
1.116 + delete _blossom_data;
1.117 + _blossom_data = new RangeMap<BlossomData>(_blossom_num);
1.118 }
1.119
1.120 if (!_node_index) {
1.121 @@ -2251,23 +2287,36 @@
1.122 _node_heap_index = new IntArcMap(_graph);
1.123 _node_data = new RangeMap<NodeData>(_node_num,
1.124 NodeData(*_node_heap_index));
1.125 + } else if (_node_data->size() != _node_num) {
1.126 + delete _node_data;
1.127 + _node_data = new RangeMap<NodeData>(_node_num,
1.128 + NodeData(*_node_heap_index));
1.129 }
1.130
1.131 if (!_tree_set) {
1.132 _tree_set_index = new IntIntMap(_blossom_num);
1.133 _tree_set = new TreeSet(*_tree_set_index);
1.134 + } else {
1.135 + _tree_set_index->resize(_blossom_num);
1.136 }
1.137 +
1.138 if (!_delta2) {
1.139 _delta2_index = new IntIntMap(_blossom_num);
1.140 _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
1.141 + } else {
1.142 + _delta2_index->resize(_blossom_num);
1.143 }
1.144 +
1.145 if (!_delta3) {
1.146 _delta3_index = new IntEdgeMap(_graph);
1.147 _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
1.148 }
1.149 +
1.150 if (!_delta4) {
1.151 _delta4_index = new IntIntMap(_blossom_num);
1.152 _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
1.153 + } else {
1.154 + _delta4_index->resize(_blossom_num);
1.155 }
1.156 }
1.157
1.158 @@ -2968,6 +3017,9 @@
1.159 void init() {
1.160 createStructures();
1.161
1.162 + _blossom_node_list.clear();
1.163 + _blossom_potential.clear();
1.164 +
1.165 for (ArcIt e(_graph); e != INVALID; ++e) {
1.166 (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
1.167 }
1.168 @@ -2981,6 +3033,12 @@
1.169
1.170 _unmatched = _node_num;
1.171
1.172 + _delta2->clear();
1.173 + _delta3->clear();
1.174 + _delta4->clear();
1.175 + _blossom_set->clear();
1.176 + _tree_set->clear();
1.177 +
1.178 int index = 0;
1.179 for (NodeIt n(_graph); n != INVALID; ++n) {
1.180 Value max = - std::numeric_limits<Value>::max();
1.181 @@ -2991,6 +3049,8 @@
1.182 }
1.183 }
1.184 (*_node_index)[n] = index;
1.185 + (*_node_data)[index].heap_index.clear();
1.186 + (*_node_data)[index].heap.clear();
1.187 (*_node_data)[index].pot = max;
1.188 int blossom =
1.189 _blossom_set->insert(n, std::numeric_limits<Value>::max());
2.1 --- a/lemon/unionfind.h Tue Mar 16 21:27:35 2010 +0100
2.2 +++ b/lemon/unionfind.h Wed Mar 17 10:29:57 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.