LEMON/LEMON-official Changeset - r914:5b926cc36a4b

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r914:5b926cc36a4b

« 908:30c77d

962:07ec2b »
959:1248d2 »
924:520514 »
920:ece1f8 »

r914:5b926cc36a4b

Tue, 16 Mar 2010 21:12:10

[Not Reviewed]

0 comments (0 inline)

deba@inf.elte.hu
deba@inf.elte.hu

Fix multiple execution bug in weighted matchings (#356) This chgset also redoes the fix of [28c7ad6f8d91] and its backpont to 1.1, [268a052c3043].

0 2 0

default

2 files changed with 71 insertions and 2 deletions:

lemon/matching.h

lemon/unionfind.h

↑ Collapse diff ↑

lemon/matching.h

Show inline comments

@@ -792,67 +792,86 @@
 		    IntEdgeMap *_delta3_index;
 		    BinHeap<Value, IntEdgeMap> *_delta3;
 		    IntIntMap *_delta4_index;
 		    BinHeap<Value, IntIntMap> *_delta4;
 		    Value _delta_sum;
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (!_matching) {
 		        _matching = new MatchingMap(_graph);
+		      }
 		      if (!_node_potential) {
 		        _node_potential = new NodePotential(_graph);
+		      }
 		      if (!_blossom_set) {
 		        _blossom_index = new IntNodeMap(_graph);
 		        _blossom_set = new BlossomSet(*_blossom_index);
 		        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
 		      } else if (_blossom_data->size() != _blossom_num) {
 		        delete _blossom_data;
 		        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
+		      }
 		      if (!_node_index) {
 		        _node_index = new IntNodeMap(_graph);
 		        _node_heap_index = new IntArcMap(_graph);
 		        _node_data = new RangeMap<NodeData>(_node_num,
-		                                              NodeData(*_node_heap_index));
 		                                            NodeData(*_node_heap_index));
 		      } else {
 		        delete _node_data;
 		        _node_data = new RangeMap<NodeData>(_node_num,
 		                                            NodeData(*_node_heap_index));
+		      }
 		      if (!_tree_set) {
 		        _tree_set_index = new IntIntMap(_blossom_num);
 		        _tree_set = new TreeSet(*_tree_set_index);
 		      } else {
 		        _tree_set_index->resize(_blossom_num);
+		      }
 		      if (!_delta1) {
 		        _delta1_index = new IntNodeMap(_graph);
 		        _delta1 = new BinHeap<Value, IntNodeMap>(*_delta1_index);
+		      }
 		      if (!_delta2) {
 		        _delta2_index = new IntIntMap(_blossom_num);
 		        _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
 		      } else {
 		        _delta2_index->resize(_blossom_num);
+		      }
 		      if (!_delta3) {
 		        _delta3_index = new IntEdgeMap(_graph);
 		        _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
+		      }
 		      if (!_delta4) {
 		        _delta4_index = new IntIntMap(_blossom_num);
 		        _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
 		      } else {
 		        _delta4_index->resize(_blossom_num);
+		      }
+		    }
 		    void destroyStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (_matching) {
 		        delete _matching;
+		      }
 		      if (_node_potential) {
 		        delete _node_potential;
+		      }
 		      if (_blossom_set) {
 		        delete _blossom_index;
 		        delete _blossom_set;
@@ -1672,56 +1691,68 @@
 		    ~MaxWeightedMatching() {
 		      destroyStructures();
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to use the
 		    /// \ref run() member function.
 		    ///@{
 		    /// \brief Initialize the algorithm
 		    ///
 		    /// This function initializes the algorithm.
 		    void init() {
 		      createStructures();
 		      _blossom_node_list.clear();
 		      _blossom_potential.clear();
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
+		      }
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        (*_delta1_index)[n] = _delta1->PRE_HEAP;
+		      }
 		      for (EdgeIt e(_graph); e != INVALID; ++e) {
 		        (*_delta3_index)[e] = _delta3->PRE_HEAP;
+		      }
 		      for (int i = 0; i < _blossom_num; ++i) {
 		        (*_delta2_index)[i] = _delta2->PRE_HEAP;
 		        (*_delta4_index)[i] = _delta4->PRE_HEAP;
+		      }
 		      _delta1->clear();
 		      _delta2->clear();
 		      _delta3->clear();
 		      _delta4->clear();
 		      _blossom_set->clear();
 		      _tree_set->clear();
 		      int index = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        Value max = 0;
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          if (_graph.target(e) == n) continue;
 		          if ((dualScale * _weight[e]) / 2 > max) {
 		            max = (dualScale * _weight[e]) / 2;
+		          }
+		        }
 		        (*_node_index)[n] = index;
 		        (*_node_data)[index].heap_index.clear();
 		        (*_node_data)[index].heap.clear();
 		        (*_node_data)[index].pot = max;
 		        _delta1->push(n, max);
 		        int blossom =
 		          _blossom_set->insert(n, std::numeric_limits<Value>::max());
 		        _tree_set->insert(blossom);
 		        (*_blossom_data)[blossom].status = EVEN;
 		        (*_blossom_data)[blossom].pred = INVALID;
 		        (*_blossom_data)[blossom].next = INVALID;
 		        (*_blossom_data)[blossom].pot = 0;
 		        (*_blossom_data)[blossom].offset = 0;
 		        ++index;
+		      }
 		      for (EdgeIt e(_graph); e != INVALID; ++e) {
 		        int si = (*_node_index)[_graph.u(e)];
@@ -2185,63 +2216,81 @@
 		    IntEdgeMap *_delta3_index;
 		    BinHeap<Value, IntEdgeMap> *_delta3;
 		    IntIntMap *_delta4_index;
 		    BinHeap<Value, IntIntMap> *_delta4;
 		    Value _delta_sum;
 		    void createStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (!_matching) {
 		        _matching = new MatchingMap(_graph);
+		      }
 		      if (!_node_potential) {
 		        _node_potential = new NodePotential(_graph);
+		      }
 		      if (!_blossom_set) {
 		        _blossom_index = new IntNodeMap(_graph);
 		        _blossom_set = new BlossomSet(*_blossom_index);
 		        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
 		      } else if (_blossom_data->size() != _blossom_num) {
 		        delete _blossom_data;
 		        _blossom_data = new RangeMap<BlossomData>(_blossom_num);
+		      }
 		      if (!_node_index) {
 		        _node_index = new IntNodeMap(_graph);
 		        _node_heap_index = new IntArcMap(_graph);
 		        _node_data = new RangeMap<NodeData>(_node_num,
 		                                            NodeData(*_node_heap_index));
 		      } else if (_node_data->size() != _node_num) {
 		        delete _node_data;
 		        _node_data = new RangeMap<NodeData>(_node_num,
 		                                            NodeData(*_node_heap_index));
+		      }
 		      if (!_tree_set) {
 		        _tree_set_index = new IntIntMap(_blossom_num);
 		        _tree_set = new TreeSet(*_tree_set_index);
 		      } else {
 		        _tree_set_index->resize(_blossom_num);
+		      }
 		      if (!_delta2) {
 		        _delta2_index = new IntIntMap(_blossom_num);
 		        _delta2 = new BinHeap<Value, IntIntMap>(*_delta2_index);
 		      } else {
 		        _delta2_index->resize(_blossom_num);
+		      }
 		      if (!_delta3) {
 		        _delta3_index = new IntEdgeMap(_graph);
 		        _delta3 = new BinHeap<Value, IntEdgeMap>(*_delta3_index);
+		      }
 		      if (!_delta4) {
 		        _delta4_index = new IntIntMap(_blossom_num);
 		        _delta4 = new BinHeap<Value, IntIntMap>(*_delta4_index);
 		      } else {
 		        _delta4_index->resize(_blossom_num);
+		      }
+		    }
 		    void destroyStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (_matching) {
 		        delete _matching;
+		      }
 		      if (_node_potential) {
 		        delete _node_potential;
+		      }
 		      if (_blossom_set) {
 		        delete _blossom_index;
 		        delete _blossom_set;
@@ -2913,53 +2962,64 @@
 		    ~MaxWeightedPerfectMatching() {
 		      destroyStructures();
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to use the
 		    /// \ref run() member function.
 		    ///@{
 		    /// \brief Initialize the algorithm
 		    ///
 		    /// This function initializes the algorithm.
 		    void init() {
 		      createStructures();
 		      _blossom_node_list.clear();
 		      _blossom_potential.clear();
 		      for (ArcIt e(_graph); e != INVALID; ++e) {
 		        (*_node_heap_index)[e] = BinHeap<Value, IntArcMap>::PRE_HEAP;
+		      }
 		      for (EdgeIt e(_graph); e != INVALID; ++e) {
 		        (*_delta3_index)[e] = _delta3->PRE_HEAP;
+		      }
 		      for (int i = 0; i < _blossom_num; ++i) {
 		        (*_delta2_index)[i] = _delta2->PRE_HEAP;
 		        (*_delta4_index)[i] = _delta4->PRE_HEAP;
+		      }
 		      _delta2->clear();
 		      _delta3->clear();
 		      _delta4->clear();
 		      _blossom_set->clear();
 		      _tree_set->clear();
 		      int index = 0;
 		      for (NodeIt n(_graph); n != INVALID; ++n) {
 		        Value max = - std::numeric_limits<Value>::max();
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          if (_graph.target(e) == n) continue;
 		          if ((dualScale * _weight[e]) / 2 > max) {
 		            max = (dualScale * _weight[e]) / 2;
+		          }
+		        }
 		        (*_node_index)[n] = index;
 		        (*_node_data)[index].heap_index.clear();
 		        (*_node_data)[index].heap.clear();
 		        (*_node_data)[index].pot = max;
 		        int blossom =
 		          _blossom_set->insert(n, std::numeric_limits<Value>::max());
 		        _tree_set->insert(blossom);
 		        (*_blossom_data)[blossom].status = EVEN;
 		        (*_blossom_data)[blossom].pred = INVALID;
 		        (*_blossom_data)[blossom].next = INVALID;
 		        (*_blossom_data)[blossom].pot = 0;
 		        (*_blossom_data)[blossom].offset = 0;
 		        ++index;
+		      }
 		      for (EdgeIt e(_graph); e != INVALID; ++e) {
 		        int si = (*_node_index)[_graph.u(e)];
 		        int ti = (*_node_index)[_graph.v(e)];

lemon/unionfind.h

Show inline comments

@@ -726,33 +726,33 @@
 		      items[idx].item = item;
 		      items[idx].cls = cls;
 		      items[idx].prev = rdx;
 		      items[idx].next = items[rdx].next;
 		      items[items[rdx].next].prev = idx;
 		      items[rdx].next = idx;
 		      index.set(item, idx);
+		    }
 		    /// \brief Clears the union-find data structure
 		    ///
 		    /// Erase each item from the data structure.
 		    void clear() {
 		      items.clear();
 		      classes.clear;
+		      classes.clear();
 		      firstClass = firstFreeClass = firstFreeItem = -1;
+		    }
 		    /// \brief Gives back the class of the \e item.
 		    ///
 		    /// Gives back the class of the \e item.
 		    int find(const Item &item) const {
 		      return items[index[item]].cls;
+		    }
 		    /// \brief Gives back a representant item of the component.
 		    ///
 		    /// Gives back a representant item of the component.
 		    Item item(int cls) const {
 		      return items[classes[cls].firstItem].item;
+		    }
@@ -1275,32 +1275,41 @@
 		    ///
 		    /// Returns true when the given class is trivial, ie. the class
 		    /// contains just one item directly.
 		    bool trivial(int cls) const {
 		      return classes[cls].left == -1;
+		    }
 		    /// \brief Constructs the union-find.
 		    ///
 		    /// Constructs the union-find.
 		    /// \brief _index The index map of the union-find. The data
 		    /// structure uses internally for store references.
 		    HeapUnionFind(ItemIntMap& _index)
 		      : index(_index), first_class(-1),
 		        first_free_class(-1), first_free_node(-1) {}
 		    /// \brief Clears the union-find data structure
 		    ///
 		    /// Erase each item from the data structure.
 		    void clear() {
 		      nodes.clear();
 		      classes.clear();
 		      first_free_node = first_free_class = first_class = -1;
+		    }
 		    /// \brief Insert a new node into a new component.
 		    ///
 		    /// Insert a new node into a new component.
 		    /// \param item The item of the new node.
 		    /// \param prio The priority of the new node.
 		    /// \return The class id of the one-item-heap.
 		    int insert(const Item& item, const Value& prio) {
 		      int id = newNode();
 		      nodes[id].item = item;
 		      nodes[id].prio = prio;
 		      nodes[id].size = 0;
 		      nodes[id].prev = -1;
 		      nodes[id].next = -1;
 		      nodes[id].left = -1;

0 comments (0 inline)

RhodeCode

Login to your account