Merge #356
authorAlpar Juttner <alpar@cs.elte.hu>
Wed, 17 Mar 2010 10:29:57 +0100
changeset 87507ec2b52e53d
parent 874 d8ea85825e02
parent 867 5b926cc36a4b
child 876 7f6e2bd76654
Merge #356
lemon/matching.h
lemon/unionfind.h
     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.