COIN-OR::LEMON - Graph Library

Changeset 867:5b926cc36a4b in lemon-1.2


Ignore:
Timestamp:
03/16/10 21:12:10 (14 years ago)
Author:
Balazs Dezso <deba@…>
Branch:
default
Children:
875:07ec2b52e53d, 886:ece1f8a3052d, 891:5205145fabf6
Phase:
public
Message:

Fix multiple execution bug in weighted matchings (#356)

This chgset also redoes the fix of [28c7ad6f8d91] and its backpont to 1.1,
[268a052c3043].

Location:
lemon
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/matching.h

    r651 r867  
    806806        _matching = new MatchingMap(_graph);
    807807      }
     808
    808809      if (!_node_potential) {
    809810        _node_potential = new NodePotential(_graph);
    810811      }
     812
    811813      if (!_blossom_set) {
    812814        _blossom_index = new IntNodeMap(_graph);
    813815        _blossom_set = new BlossomSet(*_blossom_index);
    814816        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
     817      } else if (_blossom_data->size() != _blossom_num) {
     818        delete _blossom_data;
     819        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
    815820      }
    816821
     
    819824        _node_heap_index = new IntArcMap(_graph);
    820825        _node_data = new RangeMap<NodeData>(_node_num,
    821                                               NodeData(*_node_heap_index));
     826                                            NodeData(*_node_heap_index));
     827      } else {
     828        delete _node_data;
     829        _node_data = new RangeMap<NodeData>(_node_num,
     830                                            NodeData(*_node_heap_index));
    822831      }
    823832
     
    825834        _tree_set_index = new IntIntMap(_blossom_num);
    826835        _tree_set = new TreeSet(*_tree_set_index);
    827       }
     836      } else {
     837        _tree_set_index->resize(_blossom_num);
     838      }
     839
    828840      if (!_delta1) {
    829841        _delta1_index = new IntNodeMap(_graph);
    830842        _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index);
    831843      }
     844
    832845      if (!_delta2) {
    833846        _delta2_index = new IntIntMap(_blossom_num);
    834847        _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
    835       }
     848      } else {
     849        _delta2_index->resize(_blossom_num);
     850      }
     851
    836852      if (!_delta3) {
    837853        _delta3_index = new IntEdgeMap(_graph);
    838854        _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
    839855      }
     856
    840857      if (!_delta4) {
    841858        _delta4_index = new IntIntMap(_blossom_num);
    842859        _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
     860      } else {
     861        _delta4_index->resize(_blossom_num);
    843862      }
    844863    }
     
    16861705      createStructures();
    16871706
     1707      _blossom_node_list.clear();
     1708      _blossom_potential.clear();
     1709
    16881710      for (ArcIt e(_graph); e != INVALID; ++e) {
    16891711        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
     
    16991721        (*_delta4_index)[i] = _delta4->PRE_HEAP;
    17001722      }
     1723     
     1724      _delta1->clear();
     1725      _delta2->clear();
     1726      _delta3->clear();
     1727      _delta4->clear();
     1728      _blossom_set->clear();
     1729      _tree_set->clear();
    17011730
    17021731      int index = 0;
     
    17101739        }
    17111740        (*_node_index)[n] = index;
     1741        (*_node_data)[index].heap_index.clear();
     1742        (*_node_data)[index].heap.clear();
    17121743        (*_node_data)[index].pot = max;
    17131744        _delta1->push(n, max);
     
    21992230        _matching = new MatchingMap(_graph);
    22002231      }
     2232
    22012233      if (!_node_potential) {
    22022234        _node_potential = new NodePotential(_graph);
    22032235      }
     2236
    22042237      if (!_blossom_set) {
    22052238        _blossom_index = new IntNodeMap(_graph);
    22062239        _blossom_set = new BlossomSet(*_blossom_index);
     2240        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
     2241      } else if (_blossom_data->size() != _blossom_num) {
     2242        delete _blossom_data;
    22072243        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
    22082244      }
     
    22132249        _node_data = new RangeMap<NodeData>(_node_num,
    22142250                                            NodeData(*_node_heap_index));
     2251      } else if (_node_data->size() != _node_num) {
     2252        delete _node_data;
     2253        _node_data = new RangeMap<NodeData>(_node_num,
     2254                                            NodeData(*_node_heap_index));
    22152255      }
    22162256
     
    22182258        _tree_set_index = new IntIntMap(_blossom_num);
    22192259        _tree_set = new TreeSet(*_tree_set_index);
    2220       }
     2260      } else {
     2261        _tree_set_index->resize(_blossom_num);
     2262      }
     2263
    22212264      if (!_delta2) {
    22222265        _delta2_index = new IntIntMap(_blossom_num);
    22232266        _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
    2224       }
     2267      } else {
     2268        _delta2_index->resize(_blossom_num);
     2269      }
     2270
    22252271      if (!_delta3) {
    22262272        _delta3_index = new IntEdgeMap(_graph);
    22272273        _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
    22282274      }
     2275
    22292276      if (!_delta4) {
    22302277        _delta4_index = new IntIntMap(_blossom_num);
    22312278        _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
     2279      } else {
     2280        _delta4_index->resize(_blossom_num);
    22322281      }
    22332282    }
     
    29272976      createStructures();
    29282977
     2978      _blossom_node_list.clear();
     2979      _blossom_potential.clear();
     2980
    29292981      for (ArcIt e(_graph); e != INVALID; ++e) {
    29302982        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
     
    29372989        (*_delta4_index)[i] = _delta4->PRE_HEAP;
    29382990      }
     2991
     2992      _delta2->clear();
     2993      _delta3->clear();
     2994      _delta4->clear();
     2995      _blossom_set->clear();
     2996      _tree_set->clear();
    29392997
    29402998      int index = 0;
     
    29483006        }
    29493007        (*_node_index)[n] = index;
     3008        (*_node_data)[index].heap_index.clear();
     3009        (*_node_data)[index].heap.clear();
    29503010        (*_node_data)[index].pot = max;
    29513011        int blossom =
  • lemon/unionfind.h

    r559 r867  
    740740    void clear() {
    741741      items.clear();
    742       classes.clear;
     742      classes.clear();
    743743      firstClass = firstFreeClass = firstFreeItem = -1;
    744744    }
     
    12891289        first_free_class(-1), first_free_node(-1) {}
    12901290
     1291    /// \brief Clears the union-find data structure
     1292    ///
     1293    /// Erase each item from the data structure.
     1294    void clear() {
     1295      nodes.clear();
     1296      classes.clear();
     1297      first_free_node = first_free_class = first_class = -1;
     1298    }
     1299
    12911300    /// \brief Insert a new node into a new component.
    12921301    ///
Note: See TracChangeset for help on using the changeset viewer.