Fix multiple execution bug in weighted matchings (#356)
authorBalazs Dezso <deba@inf.elte.hu>
Tue, 16 Mar 2010 21:12:10 +0100
changeset 8675b926cc36a4b
parent 852 30c77d1c0cba
child 875 07ec2b52e53d
child 882 ece1f8a3052d
child 888 5205145fabf6
Fix multiple execution bug in weighted matchings (#356)

This chgset also redoes the fix of [28c7ad6f8d91] and its backpont to 1.1,
[268a052c3043].
lemon/matching.h
lemon/unionfind.h
     1.1 --- a/lemon/matching.h	Thu Oct 15 21:04:50 2009 +0200
     1.2 +++ b/lemon/matching.h	Tue Mar 16 21:12:10 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	Thu Oct 15 21:04:50 2009 +0200
     2.2 +++ b/lemon/unionfind.h	Tue Mar 16 21:12:10 2010 +0100
     2.3 @@ -739,7 +739,7 @@
     2.4      /// Erase each item from the data structure.
     2.5      void clear() {
     2.6        items.clear();
     2.7 -      classes.clear;
     2.8 +      classes.clear();
     2.9        firstClass = firstFreeClass = firstFreeItem = -1;
    2.10      }
    2.11  
    2.12 @@ -1288,6 +1288,15 @@
    2.13        : index(_index), first_class(-1),
    2.14          first_free_class(-1), first_free_node(-1) {}
    2.15  
    2.16 +    /// \brief Clears the union-find data structure
    2.17 +    ///
    2.18 +    /// Erase each item from the data structure.
    2.19 +    void clear() {
    2.20 +      nodes.clear();
    2.21 +      classes.clear();
    2.22 +      first_free_node = first_free_class = first_class = -1;
    2.23 +    }
    2.24 +
    2.25      /// \brief Insert a new node into a new component.
    2.26      ///
    2.27      /// Insert a new node into a new component.