LEMON/LEMON-main Changeset - r868:0513ccfea967

Repositories » LEMON » LEMON-main

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

Changeset - r868:0513ccfea967

« 712:6d5f54

869:636dad »

r868:0513ccfea967

Sun, 20 Sep 2009 21:38:24

[Not Reviewed]

0 comments (0 inline)

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

General improvements in weighted matching algorithms (#314) - Fix include guard - Uniform handling of MATCHED and UNMATCHED blossoms - Prefer operations which decrease the number of trees - Fix improper use of '/=' The solved problems did not cause wrong solution.

0 1 0

default

1 file changed with 38 insertions and 157 deletions:

lemon/matching.h

157

↑ Collapse diff ↑

lemon/matching.h

Show inline comments

@@ -16,8 +16,8 @@
+		 *
 		 */
 		#ifndef LEMON_MAX_MATCHING_H
 		#define LEMON_MAX_MATCHING_H
 		#ifndef LEMON_MATCHING_H
 		#define LEMON_MATCHING_H
 		#include <vector>
 		#include <queue>
@@ -745,7 +745,7 @@
 		    typedef RangeMap<int> IntIntMap;
 		    enum Status {
-		      EVEN = -1, MATCHED = 0, ODD = 1, UNMATCHED = -2
 		      EVEN = -1, MATCHED = 0, ODD = 1
 		    };
 		    typedef HeapUnionFind<Value, IntNodeMap> BlossomSet;
@@ -844,9 +844,6 @@
+		    }
 		    void destroyStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (_matching) {
 		        delete _matching;
+		      }
@@ -922,10 +919,6 @@
 		            if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
 		              _delta3->push(e, rw / 2);
+		            }
 		          } else if ((*_blossom_data)[vb].status == UNMATCHED) {
 		            if (_delta3->state(e) != _delta3->IN_HEAP) {
 		              _delta3->push(e, rw);
+		            }
 		          } else {
 		            typename std::map<int, Arc>::iterator it =
 		              (*_node_data)[vi].heap_index.find(tree);
@@ -1036,11 +1029,6 @@
+		                }
+		              }
+		            }
 		          } else if ((*_blossom_data)[vb].status == UNMATCHED) {
 		            if (_delta3->state(e) == _delta3->IN_HEAP) {
 		              _delta3->erase(e);
+		            }
 		          } else {
 		            typename std::map<int, Arc>::iterator it =
@@ -1117,10 +1105,6 @@
 		            if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
 		              _delta3->push(e, rw / 2);
+		            }
 		          } else if ((*_blossom_data)[vb].status == UNMATCHED) {
 		            if (_delta3->state(e) != _delta3->IN_HEAP) {
 		              _delta3->push(e, rw);
+		            }
 		          } else {
 		            typename std::map<int, Arc>::iterator it =
@@ -1157,101 +1141,6 @@
 		      (*_blossom_data)[blossom].offset = 0;
+		    }
 		    void matchedToUnmatched(int blossom) {
 		      if (_delta2->state(blossom) == _delta2->IN_HEAP) {
 		        _delta2->erase(blossom);
+		      }
 		      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
 		           n != INVALID; ++n) {
 		        int ni = (*_node_index)[n];
 		        _blossom_set->increase(n, std::numeric_limits<Value>::max());
 		        (*_node_data)[ni].heap.clear();
 		        (*_node_data)[ni].heap_index.clear();
 		        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node v = _graph.target(e);
 		          int vb = _blossom_set->find(v);
 		          int vi = (*_node_index)[v];
 		          Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot -
 		            dualScale * _weight[e];
 		          if ((*_blossom_data)[vb].status == EVEN) {
 		            if (_delta3->state(e) != _delta3->IN_HEAP) {
 		              _delta3->push(e, rw);
+		            }
+		          }
+		        }
+		      }
+		    }
 		    void unmatchedToMatched(int blossom) {
 		      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
 		           n != INVALID; ++n) {
 		        int ni = (*_node_index)[n];
 		        for (InArcIt e(_graph, n); e != INVALID; ++e) {
 		          Node v = _graph.source(e);
 		          int vb = _blossom_set->find(v);
 		          int vi = (*_node_index)[v];
 		          Value rw = (*_node_data)[ni].pot + (*_node_data)[vi].pot -
 		            dualScale * _weight[e];
 		          if (vb == blossom) {
 		            if (_delta3->state(e) == _delta3->IN_HEAP) {
 		              _delta3->erase(e);
+		            }
 		          } else if ((*_blossom_data)[vb].status == EVEN) {
 		            if (_delta3->state(e) == _delta3->IN_HEAP) {
 		              _delta3->erase(e);
+		            }
 		            int vt = _tree_set->find(vb);
 		            Arc r = _graph.oppositeArc(e);
 		            typename std::map<int, Arc>::iterator it =
 		              (*_node_data)[ni].heap_index.find(vt);
 		            if (it != (*_node_data)[ni].heap_index.end()) {
 		              if ((*_node_data)[ni].heap[it->second] > rw) {
 		                (*_node_data)[ni].heap.replace(it->second, r);
 		                (*_node_data)[ni].heap.decrease(r, rw);
 		                it->second = r;
+		              }
 		            } else {
 		              (*_node_data)[ni].heap.push(r, rw);
 		              (*_node_data)[ni].heap_index.insert(std::make_pair(vt, r));
+		            }
 		            if ((*_blossom_set)[n] > (*_node_data)[ni].heap.prio()) {
 		              _blossom_set->decrease(n, (*_node_data)[ni].heap.prio());
 		              if (_delta2->state(blossom) != _delta2->IN_HEAP) {
 		                _delta2->push(blossom, _blossom_set->classPrio(blossom) -
 		                             (*_blossom_data)[blossom].offset);
 		              } else if ((*_delta2)[blossom] > _blossom_set->classPrio(blossom)-
 		                         (*_blossom_data)[blossom].offset){
 		                _delta2->decrease(blossom, _blossom_set->classPrio(blossom) -
 		                                 (*_blossom_data)[blossom].offset);
+		              }
+		            }
 		          } else if ((*_blossom_data)[vb].status == UNMATCHED) {
 		            if (_delta3->state(e) == _delta3->IN_HEAP) {
 		              _delta3->erase(e);
+		            }
+		          }
+		        }
+		      }
+		    }
 		    void alternatePath(int even, int tree) {
 		      int odd;
@@ -1294,39 +1183,42 @@
 		      alternatePath(blossom, tree);
 		      destroyTree(tree);
 		      (*_blossom_data)[blossom].status = UNMATCHED;
 		      (*_blossom_data)[blossom].base = node;
 		      matchedToUnmatched(blossom);
+		    }
+		      (*_blossom_data)[blossom].next = INVALID;
+		    }
 		    void augmentOnEdge(const Edge& edge) {
 		      int left = _blossom_set->find(_graph.u(edge));
 		      int right = _blossom_set->find(_graph.v(edge));
 		      if ((*_blossom_data)[left].status == EVEN) {
 		        int left_tree = _tree_set->find(left);
 		        alternatePath(left, left_tree);
 		        destroyTree(left_tree);
 		      } else {
 		        (*_blossom_data)[left].status = MATCHED;
 		        unmatchedToMatched(left);
+		      }
 		      if ((*_blossom_data)[right].status == EVEN) {
 		        int right_tree = _tree_set->find(right);
 		        alternatePath(right, right_tree);
 		        destroyTree(right_tree);
 		      } else {
 		        (*_blossom_data)[right].status = MATCHED;
 		        unmatchedToMatched(right);
+		      }
 		      (*_blossom_data)[left].next = _graph.direct(edge, true);
 		      (*_blossom_data)[right].next = _graph.direct(edge, false);
+		    }
 		    void augmentOnArc(const Arc& arc) {
 		      int left = _blossom_set->find(_graph.source(arc));
 		      int right = _blossom_set->find(_graph.target(arc));
 		      (*_blossom_data)[left].status = MATCHED;
 		      int right_tree = _tree_set->find(right);
 		      alternatePath(right, right_tree);
 		      destroyTree(right_tree);
 		      (*_blossom_data)[left].next = arc;
 		      (*_blossom_data)[right].next = _graph.oppositeArc(arc);
+		    }
 		    void extendOnArc(const Arc& arc) {
 		      int base = _blossom_set->find(_graph.target(arc));
 		      int tree = _tree_set->find(base);
@@ -1629,7 +1521,7 @@
+		      }
 		      for (int i = 0; i < int(blossoms.size()); ++i) {
-		        if ((*_blossom_data)[blossoms[i]].status == MATCHED) {
+		        if ((*_blossom_data)[blossoms[i]].next != INVALID) {
 		          Value offset = (*_blossom_data)[blossoms[i]].offset;
 		          (*_blossom_data)[blossoms[i]].pot += 2 * offset;
@@ -1757,12 +1649,11 @@
 		        Value d4 = !_delta4->empty() ?
 		          _delta4->prio() : std::numeric_limits<Value>::max();
-		        _delta_sum = d1; OpType ot = D1;
+		        _delta_sum = d3; OpType ot = D3;
 		        if (d1 < _delta_sum) { _delta_sum = d1; ot = D1; }
 		        if (d2 < _delta_sum) { _delta_sum = d2; ot = D2; }
 		        if (d3 < _delta_sum) { _delta_sum = d3; ot = D3; }
 		        if (d4 < _delta_sum) { _delta_sum = d4; ot = D4; }
 		        switch (ot) {
 		        case D1:
+		          {
@@ -1775,8 +1666,13 @@
+		          {
 		            int blossom = _delta2->top();
 		            Node n = _blossom_set->classTop(blossom);
 		            Arc e = (*_node_data)[(*_node_index)[n]].heap.top();
 		            extendOnArc(e);
 		            Arc a = (*_node_data)[(*_node_index)[n]].heap.top();
 		            if ((*_blossom_data)[blossom].next == INVALID) {
 		              augmentOnArc(a);
 		              --unmatched;
 		            } else {
 		              extendOnArc(a);
+		            }
+		          }
 		          break;
 		        case D3:
@@ -1789,20 +1685,8 @@
 		            if (left_blossom == right_blossom) {
 		              _delta3->pop();
 		            } else {
 		              int left_tree;
 		              if ((*_blossom_data)[left_blossom].status == EVEN) {
 		                left_tree = _tree_set->find(left_blossom);
 		              } else {
 		                left_tree = -1;
 		                ++unmatched;
+		              }
 		              int right_tree;
 		              if ((*_blossom_data)[right_blossom].status == EVEN) {
 		                right_tree = _tree_set->find(right_blossom);
 		              } else {
 		                right_tree = -1;
 		                ++unmatched;
+		              }
 		              int left_tree = _tree_set->find(left_blossom);
 		              int right_tree = _tree_set->find(right_blossom);
 		              if (left_tree == right_tree) {
 		                shrinkOnEdge(e, left_tree);
@@ -1856,7 +1740,7 @@
 		          sum += _weight[(*_matching)[n]];
+		        }
+		      }
-		      return sum /= 2;
 		      return sum / 2;
+		    }
 		    /// \brief Return the size (cardinality) of the matching.
@@ -2233,9 +2117,6 @@
+		    }
 		    void destroyStructures() {
 		      _node_num = countNodes(_graph);
 		      _blossom_num = _node_num * 3 / 2;
 		      if (_matching) {
 		        delete _matching;
+		      }
@@ -2991,8 +2872,8 @@
 		        Value d4 = !_delta4->empty() ?
 		          _delta4->prio() : std::numeric_limits<Value>::max();
 		        _delta_sum = d2; OpType ot = D2;
 		        if (d3 < _delta_sum) { _delta_sum = d3; ot = D3; }
 		        _delta_sum = d3; OpType ot = D3;
 		        if (d2 < _delta_sum) { _delta_sum = d2; ot = D2; }
 		        if (d4 < _delta_sum) { _delta_sum = d4; ot = D4; }
 		        if (_delta_sum == std::numeric_limits<Value>::max()) {
@@ -3074,7 +2955,7 @@
 		          sum += _weight[(*_matching)[n]];
+		        }
+		      }
-		      return sum /= 2;
 		      return sum / 2;
+		    }
 		    /// \brief Return \c true if the given edge is in the matching.
@@ -3241,4 +3122,4 @@
 		} //END OF NAMESPACE LEMON
-		#endif //LEMON_MAX_MATCHING_H
+		#endif //LEMON_MATCHING_H

0 comments (0 inline)

RhodeCode

Login to your account