LEMON/LEMON-main Changeset - r867:5b926cc36a4b

Repositories » LEMON » LEMON-main

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

Changeset - r867:5b926cc36a4b

« 852:30c77d

888:520514 »
882:ece1f8 »
875:07ec2b »

r867: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

@@ -712,227 +712,246 @@
 		      std::numeric_limits<Value>::is_integer ? 4 : 1;
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    typedef typename Graph::template NodeMap<Value> NodePotential;
 		    typedef std::vector<Node> BlossomNodeList;
 		    struct BlossomVariable {
 		      int begin, end;
 		      Value value;
 		      BlossomVariable(int _begin, int _end, Value _value)
 		        : begin(_begin), end(_end), value(_value) {}
 		    };
 		    typedef std::vector<BlossomVariable> BlossomPotential;
 		    const Graph& _graph;
 		    const WeightMap& _weight;
 		    MatchingMap* _matching;
 		    NodePotential* _node_potential;
 		    BlossomPotential _blossom_potential;
 		    BlossomNodeList _blossom_node_list;
 		    int _node_num;
 		    int _blossom_num;
 		    typedef RangeMap<int> IntIntMap;
 		    enum Status {
 		      EVEN = -1, MATCHED = 0, ODD = 1, UNMATCHED = -2
 		    };
 		    typedef HeapUnionFind<Value, IntNodeMap> BlossomSet;
 		    struct BlossomData {
 		      int tree;
 		      Status status;
 		      Arc pred, next;
 		      Value pot, offset;
 		      Node base;
 		    };
 		    IntNodeMap *_blossom_index;
 		    BlossomSet *_blossom_set;
 		    RangeMap<BlossomData>* _blossom_data;
 		    IntNodeMap *_node_index;
 		    IntArcMap *_node_heap_index;
 		    struct NodeData {
 		      NodeData(IntArcMap& node_heap_index)
 		        : heap(node_heap_index) {}
 		      int blossom;
 		      Value pot;
 		      BinHeap<Value, IntArcMap> heap;
 		      std::map<int, Arc> heap_index;
 		      int tree;
 		    };
 		    RangeMap<NodeData>* _node_data;
 		    typedef ExtendFindEnum<IntIntMap> TreeSet;
 		    IntIntMap *_tree_set_index;
 		    TreeSet *_tree_set;
 		    IntNodeMap *_delta1_index;
 		    BinHeap<Value, IntNodeMap> *_delta1;
 		    IntIntMap *_delta2_index;
 		    BinHeap<Value, IntIntMap> *_delta2;
 		    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;
 		        delete _blossom_data;
+		      }
 		      if (_node_index) {
 		        delete _node_index;
 		        delete _node_heap_index;
 		        delete _node_data;
+		      }
 		      if (_tree_set) {
 		        delete _tree_set_index;
 		        delete _tree_set;
+		      }
 		      if (_delta1) {
 		        delete _delta1_index;
 		        delete _delta1;
+		      }
 		      if (_delta2) {
 		        delete _delta2_index;
 		        delete _delta2;
+		      }
 		      if (_delta3) {
 		        delete _delta3_index;
 		        delete _delta3;
+		      }
 		      if (_delta4) {
 		        delete _delta4_index;
 		        delete _delta4;
+		      }
+		    }
 		    void matchedToEven(int blossom, int tree) {
 		      if (_delta2->state(blossom) == _delta2->IN_HEAP) {
 		        _delta2->erase(blossom);
+		      }
 		      if (!_blossom_set->trivial(blossom)) {
 		        (*_blossom_data)[blossom].pot -=
 * (_delta_sum - (*_blossom_data)[blossom].offset);
+		      }
 		      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
 		           n != INVALID; ++n) {
 		        _blossom_set->increase(n, std::numeric_limits<Value>::max());
 		        int ni = (*_node_index)[n];
 		        (*_node_data)[ni].heap.clear();
 		        (*_node_data)[ni].heap_index.clear();
 		        (*_node_data)[ni].pot += _delta_sum - (*_blossom_data)[blossom].offset;
 		        _delta1->push(n, (*_node_data)[ni].pot);
 		        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 ((*_blossom_data)[vb].status == EVEN) {
 		            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);
 		            if (it != (*_node_data)[vi].heap_index.end()) {
 		              if ((*_node_data)[vi].heap[it->second] > rw) {
 		                (*_node_data)[vi].heap.replace(it->second, e);
 		                (*_node_data)[vi].heap.decrease(e, rw);
 		                it->second = e;
+		              }
@@ -1592,216 +1611,228 @@
 		        (*_matching)[base] = matching;
 		        _blossom_node_list.push_back(base);
 		        (*_node_potential)[base] = pot;
 		      } else {
 		        Value pot = (*_blossom_data)[blossom].pot;
 		        int bn = _blossom_node_list.size();
 		        std::vector<int> subblossoms;
 		        _blossom_set->split(blossom, std::back_inserter(subblossoms));
 		        int b = _blossom_set->find(base);
 		        int ib = -1;
 		        for (int i = 0; i < int(subblossoms.size()); ++i) {
 		          if (subblossoms[i] == b) { ib = i; break; }
+		        }
 		        for (int i = 1; i < int(subblossoms.size()); i += 2) {
 		          int sb = subblossoms[(ib + i) % subblossoms.size()];
 		          int tb = subblossoms[(ib + i + 1) % subblossoms.size()];
 		          Arc m = (*_blossom_data)[tb].next;
 		          extractBlossom(sb, _graph.target(m), _graph.oppositeArc(m));
 		          extractBlossom(tb, _graph.source(m), m);
+		        }
 		        extractBlossom(subblossoms[ib], base, matching);
 		        int en = _blossom_node_list.size();
 		        _blossom_potential.push_back(BlossomVariable(bn, en, pot));
+		      }
+		    }
 		    void extractMatching() {
 		      std::vector<int> blossoms;
 		      for (typename BlossomSet::ClassIt c(*_blossom_set); c != INVALID; ++c) {
 		        blossoms.push_back(c);
+		      }
 		      for (int i = 0; i < int(blossoms.size()); ++i) {
 		        if ((*_blossom_data)[blossoms[i]].status == MATCHED) {
 		          Value offset = (*_blossom_data)[blossoms[i]].offset;
 		          (*_blossom_data)[blossoms[i]].pot += 2 * offset;
 		          for (typename BlossomSet::ItemIt n(*_blossom_set, blossoms[i]);
 		               n != INVALID; ++n) {
 		            (*_node_data)[(*_node_index)[n]].pot -= offset;
+		          }
 		          Arc matching = (*_blossom_data)[blossoms[i]].next;
 		          Node base = _graph.source(matching);
 		          extractBlossom(blossoms[i], base, matching);
 		        } else {
 		          Node base = (*_blossom_data)[blossoms[i]].base;
 		          extractBlossom(blossoms[i], base, INVALID);
+		        }
+		      }
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor.
 		    MaxWeightedMatching(const Graph& graph, const WeightMap& weight)
 		      : _graph(graph), _weight(weight), _matching(0),
 		        _node_potential(0), _blossom_potential(), _blossom_node_list(),
 		        _node_num(0), _blossom_num(0),
 		        _blossom_index(0), _blossom_set(0), _blossom_data(0),
 		        _node_index(0), _node_heap_index(0), _node_data(0),
 		        _tree_set_index(0), _tree_set(0),
 		        _delta1_index(0), _delta1(0),
 		        _delta2_index(0), _delta2(0),
 		        _delta3_index(0), _delta3(0),
 		        _delta4_index(0), _delta4(0),
 		        _delta_sum() {}
 		    ~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)];
 		        int ti = (*_node_index)[_graph.v(e)];
 		        if (_graph.u(e) != _graph.v(e)) {
 		          _delta3->push(e, ((*_node_data)[si].pot + (*_node_data)[ti].pot -
 		                            dualScale * _weight[e]) / 2);
+		        }
+		      }
+		    }
 		    /// \brief Start the algorithm
 		    ///
 		    /// This function starts the algorithm.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    void start() {
 		      enum OpType {
 		        D1, D2, D3, D4
 		      };
 		      int unmatched = _node_num;
 		      while (unmatched > 0) {
 		        Value d1 = !_delta1->empty() ?
 		          _delta1->prio() : std::numeric_limits<Value>::max();
 		        Value d2 = !_delta2->empty() ?
 		          _delta2->prio() : std::numeric_limits<Value>::max();
 		        Value d3 = !_delta3->empty() ?
 		          _delta3->prio() : std::numeric_limits<Value>::max();
 		        Value d4 = !_delta4->empty() ?
 		          _delta4->prio() : std::numeric_limits<Value>::max();
 		        _delta_sum = d1; OpType 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:
+		          {
 		            Node n = _delta1->top();
 		            unmatchNode(n);
 		            --unmatched;
+		          }
 		          break;
 		        case D2:
+		          {
 		            int blossom = _delta2->top();
 		            Node n = _blossom_set->classTop(blossom);
 		            Arc e = (*_node_data)[(*_node_index)[n]].heap.top();
 		            extendOnArc(e);
+		          }
 		          break;
 		        case D3:
+		          {
 		            Edge e = _delta3->top();
 		            int left_blossom = _blossom_set->find(_graph.u(e));
 		            int right_blossom = _blossom_set->find(_graph.v(e));
 		            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;
+		              }
 		              if (left_tree == right_tree) {
@@ -2105,223 +2136,241 @@
 		      std::numeric_limits<Value>::is_integer ? 4 : 1;
 		    /// The type of the matching map
 		    typedef typename Graph::template NodeMap<typename Graph::Arc>
 		    MatchingMap;
 		  private:
 		    TEMPLATE_GRAPH_TYPEDEFS(Graph);
 		    typedef typename Graph::template NodeMap<Value> NodePotential;
 		    typedef std::vector<Node> BlossomNodeList;
 		    struct BlossomVariable {
 		      int begin, end;
 		      Value value;
 		      BlossomVariable(int _begin, int _end, Value _value)
 		        : begin(_begin), end(_end), value(_value) {}
 		    };
 		    typedef std::vector<BlossomVariable> BlossomPotential;
 		    const Graph& _graph;
 		    const WeightMap& _weight;
 		    MatchingMap* _matching;
 		    NodePotential* _node_potential;
 		    BlossomPotential _blossom_potential;
 		    BlossomNodeList _blossom_node_list;
 		    int _node_num;
 		    int _blossom_num;
 		    typedef RangeMap<int> IntIntMap;
 		    enum Status {
 		      EVEN = -1, MATCHED = 0, ODD = 1
 		    };
 		    typedef HeapUnionFind<Value, IntNodeMap> BlossomSet;
 		    struct BlossomData {
 		      int tree;
 		      Status status;
 		      Arc pred, next;
 		      Value pot, offset;
 		    };
 		    IntNodeMap *_blossom_index;
 		    BlossomSet *_blossom_set;
 		    RangeMap<BlossomData>* _blossom_data;
 		    IntNodeMap *_node_index;
 		    IntArcMap *_node_heap_index;
 		    struct NodeData {
 		      NodeData(IntArcMap& node_heap_index)
 		        : heap(node_heap_index) {}
 		      int blossom;
 		      Value pot;
 		      BinHeap<Value, IntArcMap> heap;
 		      std::map<int, Arc> heap_index;
 		      int tree;
 		    };
 		    RangeMap<NodeData>* _node_data;
 		    typedef ExtendFindEnum<IntIntMap> TreeSet;
 		    IntIntMap *_tree_set_index;
 		    TreeSet *_tree_set;
 		    IntIntMap *_delta2_index;
 		    BinHeap<Value, IntIntMap> *_delta2;
 		    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;
 		        delete _blossom_data;
+		      }
 		      if (_node_index) {
 		        delete _node_index;
 		        delete _node_heap_index;
 		        delete _node_data;
+		      }
 		      if (_tree_set) {
 		        delete _tree_set_index;
 		        delete _tree_set;
+		      }
 		      if (_delta2) {
 		        delete _delta2_index;
 		        delete _delta2;
+		      }
 		      if (_delta3) {
 		        delete _delta3_index;
 		        delete _delta3;
+		      }
 		      if (_delta4) {
 		        delete _delta4_index;
 		        delete _delta4;
+		      }
+		    }
 		    void matchedToEven(int blossom, int tree) {
 		      if (_delta2->state(blossom) == _delta2->IN_HEAP) {
 		        _delta2->erase(blossom);
+		      }
 		      if (!_blossom_set->trivial(blossom)) {
 		        (*_blossom_data)[blossom].pot -=
 * (_delta_sum - (*_blossom_data)[blossom].offset);
+		      }
 		      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);
 		           n != INVALID; ++n) {
 		        _blossom_set->increase(n, std::numeric_limits<Value>::max());
 		        int ni = (*_node_index)[n];
 		        (*_node_data)[ni].heap.clear();
 		        (*_node_data)[ni].heap_index.clear();
 		        (*_node_data)[ni].pot += _delta_sum - (*_blossom_data)[blossom].offset;
 		        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 ((*_blossom_data)[vb].status == EVEN) {
 		            if (_delta3->state(e) != _delta3->IN_HEAP && blossom != vb) {
 		              _delta3->push(e, rw / 2);
+		            }
 		          } else {
 		            typename std::map<int, Arc>::iterator it =
 		              (*_node_data)[vi].heap_index.find(tree);
 		            if (it != (*_node_data)[vi].heap_index.end()) {
 		              if ((*_node_data)[vi].heap[it->second] > rw) {
 		                (*_node_data)[vi].heap.replace(it->second, e);
 		                (*_node_data)[vi].heap.decrease(e, rw);
 		                it->second = e;
+		              }
 		            } else {
 		              (*_node_data)[vi].heap.push(e, rw);
 		              (*_node_data)[vi].heap_index.insert(std::make_pair(tree, e));
+		            }
 		            if ((*_blossom_set)[v] > (*_node_data)[vi].heap.prio()) {
 		              _blossom_set->decrease(v, (*_node_data)[vi].heap.prio());
 		              if ((*_blossom_data)[vb].status == MATCHED) {
 		                if (_delta2->state(vb) != _delta2->IN_HEAP) {
@@ -2833,213 +2882,224 @@
+		    }
 		    void extractBlossom(int blossom, const Node& base, const Arc& matching) {
 		      if (_blossom_set->trivial(blossom)) {
 		        int bi = (*_node_index)[base];
 		        Value pot = (*_node_data)[bi].pot;
 		        (*_matching)[base] = matching;
 		        _blossom_node_list.push_back(base);
 		        (*_node_potential)[base] = pot;
 		      } else {
 		        Value pot = (*_blossom_data)[blossom].pot;
 		        int bn = _blossom_node_list.size();
 		        std::vector<int> subblossoms;
 		        _blossom_set->split(blossom, std::back_inserter(subblossoms));
 		        int b = _blossom_set->find(base);
 		        int ib = -1;
 		        for (int i = 0; i < int(subblossoms.size()); ++i) {
 		          if (subblossoms[i] == b) { ib = i; break; }
+		        }
 		        for (int i = 1; i < int(subblossoms.size()); i += 2) {
 		          int sb = subblossoms[(ib + i) % subblossoms.size()];
 		          int tb = subblossoms[(ib + i + 1) % subblossoms.size()];
 		          Arc m = (*_blossom_data)[tb].next;
 		          extractBlossom(sb, _graph.target(m), _graph.oppositeArc(m));
 		          extractBlossom(tb, _graph.source(m), m);
+		        }
 		        extractBlossom(subblossoms[ib], base, matching);
 		        int en = _blossom_node_list.size();
 		        _blossom_potential.push_back(BlossomVariable(bn, en, pot));
+		      }
+		    }
 		    void extractMatching() {
 		      std::vector<int> blossoms;
 		      for (typename BlossomSet::ClassIt c(*_blossom_set); c != INVALID; ++c) {
 		        blossoms.push_back(c);
+		      }
 		      for (int i = 0; i < int(blossoms.size()); ++i) {
 		        Value offset = (*_blossom_data)[blossoms[i]].offset;
 		        (*_blossom_data)[blossoms[i]].pot += 2 * offset;
 		        for (typename BlossomSet::ItemIt n(*_blossom_set, blossoms[i]);
 		             n != INVALID; ++n) {
 		          (*_node_data)[(*_node_index)[n]].pot -= offset;
+		        }
 		        Arc matching = (*_blossom_data)[blossoms[i]].next;
 		        Node base = _graph.source(matching);
 		        extractBlossom(blossoms[i], base, matching);
+		      }
+		    }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor.
 		    MaxWeightedPerfectMatching(const Graph& graph, const WeightMap& weight)
 		      : _graph(graph), _weight(weight), _matching(0),
 		        _node_potential(0), _blossom_potential(), _blossom_node_list(),
 		        _node_num(0), _blossom_num(0),
 		        _blossom_index(0), _blossom_set(0), _blossom_data(0),
 		        _node_index(0), _node_heap_index(0), _node_data(0),
 		        _tree_set_index(0), _tree_set(0),
 		        _delta2_index(0), _delta2(0),
 		        _delta3_index(0), _delta3(0),
 		        _delta4_index(0), _delta4(0),
 		        _delta_sum() {}
 		    ~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)];
 		        if (_graph.u(e) != _graph.v(e)) {
 		          _delta3->push(e, ((*_node_data)[si].pot + (*_node_data)[ti].pot -
 		                            dualScale * _weight[e]) / 2);
+		        }
+		      }
+		    }
 		    /// \brief Start the algorithm
 		    ///
 		    /// This function starts the algorithm.
 		    ///
 		    /// \pre \ref init() must be called before using this function.
 		    bool start() {
 		      enum OpType {
 		        D2, D3, D4
 		      };
 		      int unmatched = _node_num;
 		      while (unmatched > 0) {
 		        Value d2 = !_delta2->empty() ?
 		          _delta2->prio() : std::numeric_limits<Value>::max();
 		        Value d3 = !_delta3->empty() ?
 		          _delta3->prio() : std::numeric_limits<Value>::max();
 		        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; }
 		        if (d4 < _delta_sum) { _delta_sum = d4; ot = D4; }
 		        if (_delta_sum == std::numeric_limits<Value>::max()) {
 		          return false;
+		        }
 		        switch (ot) {
 		        case D2:
+		          {
 		            int blossom = _delta2->top();
 		            Node n = _blossom_set->classTop(blossom);
 		            Arc e = (*_node_data)[(*_node_index)[n]].heap.top();
 		            extendOnArc(e);
+		          }
 		          break;
 		        case D3:
+		          {
 		            Edge e = _delta3->top();
 		            int left_blossom = _blossom_set->find(_graph.u(e));
 		            int right_blossom = _blossom_set->find(_graph.v(e));
 		            if (left_blossom == right_blossom) {
 		              _delta3->pop();
 		            } else {
 		              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);
 		              } else {
 		                augmentOnEdge(e);
 		                unmatched -= 2;
+		              }
+		            }
 		          } break;
 		        case D4:
 		          splitBlossom(_delta4->top());
 		          break;
+		        }
+		      }
 		      extractMatching();
 		      return true;
+		    }
 		    /// \brief Run the algorithm.
 		    ///
 		    /// This method runs the \c %MaxWeightedPerfectMatching algorithm.
 		    ///
 		    /// \note mwpm.run() is just a shortcut of the following code.

lemon/unionfind.h

Show inline comments

@@ -646,193 +646,193 @@
 		    struct ItemT {
 		      int cls;
 		      Item item;
 		      int next, prev;
 		    };
 		    std::vector<ItemT> items;
 		    int firstFreeItem;
 		    struct ClassT {
 		      int firstItem;
 		      int next, prev;
 		    };
 		    std::vector<ClassT> classes;
 		    int firstClass, firstFreeClass;
 		    int newClass() {
 		      if (firstFreeClass != -1) {
 		        int cdx = firstFreeClass;
 		        firstFreeClass = classes[cdx].next;
 		        return cdx;
 		      } else {
 		        classes.push_back(ClassT());
 		        return classes.size() - 1;
+		      }
+		    }
 		    int newItem() {
 		      if (firstFreeItem != -1) {
 		        int idx = firstFreeItem;
 		        firstFreeItem = items[idx].next;
 		        return idx;
 		      } else {
 		        items.push_back(ItemT());
 		        return items.size() - 1;
+		      }
+		    }
 		  public:
 		    /// \brief Constructor
 		    ExtendFindEnum(ItemIntMap& _index)
 		      : index(_index), items(), firstFreeItem(-1),
 		        classes(), firstClass(-1), firstFreeClass(-1) {}
 		    /// \brief Inserts the given element into a new component.
 		    ///
 		    /// This method creates a new component consisting only of the
 		    /// given element.
 		    int insert(const Item& item) {
 		      int cdx = newClass();
 		      classes[cdx].prev = -1;
 		      classes[cdx].next = firstClass;
 		      if (firstClass != -1) {
 		        classes[firstClass].prev = cdx;
+		      }
 		      firstClass = cdx;
 		      int idx = newItem();
 		      items[idx].item = item;
 		      items[idx].cls = cdx;
 		      items[idx].prev = idx;
 		      items[idx].next = idx;
 		      classes[cdx].firstItem = idx;
 		      index.set(item, idx);
 		      return cdx;
+		    }
 		    /// \brief Inserts the given element into the given component.
 		    ///
 		    /// This methods inserts the element \e item a into the \e cls class.
 		    void insert(const Item& item, int cls) {
 		      int idx = newItem();
 		      int rdx = classes[cls].firstItem;
 		      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;
+		    }
 		    /// \brief Removes the given element from the structure.
 		    ///
 		    /// Removes the element from its component and if the component becomes
 		    /// empty then removes that component from the component list.
 		    ///
 		    /// \warning It is an error to remove an element which is not in
 		    /// the structure.
 		    void erase(const Item &item) {
 		      int idx = index[item];
 		      int cdx = items[idx].cls;
 		      if (idx == items[idx].next) {
 		        if (classes[cdx].prev != -1) {
 		          classes[classes[cdx].prev].next = classes[cdx].next;
 		        } else {
 		          firstClass = classes[cdx].next;
+		        }
 		        if (classes[cdx].next != -1) {
 		          classes[classes[cdx].next].prev = classes[cdx].prev;
+		        }
 		        classes[cdx].next = firstFreeClass;
 		        firstFreeClass = cdx;
 		      } else {
 		        classes[cdx].firstItem = items[idx].next;
 		        items[items[idx].next].prev = items[idx].prev;
 		        items[items[idx].prev].next = items[idx].next;
+		      }
 		      items[idx].next = firstFreeItem;
 		      firstFreeItem = idx;
+		    }
 		    /// \brief Removes the component of the given element from the structure.
 		    ///
 		    /// Removes the component of the given element from the structure.
 		    ///
 		    /// \warning It is an error to give an element which is not in the
 		    /// structure.
 		    void eraseClass(int cdx) {
 		      int idx = classes[cdx].firstItem;
 		      items[items[idx].prev].next = firstFreeItem;
 		      firstFreeItem = idx;
 		      if (classes[cdx].prev != -1) {
 		        classes[classes[cdx].prev].next = classes[cdx].next;
 		      } else {
 		        firstClass = classes[cdx].next;
+		      }
 		      if (classes[cdx].next != -1) {
 		        classes[classes[cdx].next].prev = classes[cdx].prev;
+		      }
 		      classes[cdx].next = firstFreeClass;
 		      firstFreeClass = cdx;
+		    }
 		    /// \brief LEMON style iterator for the classes.
 		    ///
 		    /// ClassIt is a lemon style iterator for the components. It iterates
 		    /// on the ids of classes.
 		    class ClassIt {
 		    public:
 		      /// \brief Constructor of the iterator
 		      ///
 		      /// Constructor of the iterator
 		      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {
 		        cdx = extendFind->firstClass;
+		      }
 		      /// \brief Constructor to get invalid iterator
 		      ///
 		      /// Constructor to get invalid iterator
 		      ClassIt(Invalid) : extendFind(0), cdx(-1) {}
 		      /// \brief Increment operator
 		      ///
 		      /// It steps to the next representant item.
 		      ClassIt& operator++() {
 		        cdx = extendFind->classes[cdx].next;
@@ -1195,192 +1195,201 @@
 		              int ld = nodes[nodes[jd].next].left;
 		              popLeft(nodes[jd].next);
 		              pushRight(jd, ld);
 		              if (less(ld, nodes[jd].left) ||
 		                  nodes[ld].item == nodes[pd].item) {
 		                nodes[jd].item = nodes[ld].item;
 		                nodes[jd].prio = nodes[ld].prio;
+		              }
 		              if (nodes[nodes[jd].next].item == nodes[ld].item) {
 		                setPrio(nodes[jd].next);
+		              }
 		              jd = nodes[jd].left;
+		            }
+		          }
 		        } else {
 		          jd = nodes[jd].left;
+		        }
+		      }
+		    }
 		    void repairRight(int id) {
 		      int jd = ~(classes[id].parent);
 		      while (nodes[jd].right != -1) {
 		        int kd = nodes[jd].right;
 		        if (nodes[jd].size == 1) {
 		          if (nodes[jd].parent < 0) {
 		            classes[id].parent = ~kd;
 		            classes[id].depth -= 1;
 		            nodes[kd].parent = ~id;
 		            deleteNode(jd);
 		            jd = kd;
 		          } else {
 		            int pd = nodes[jd].parent;
 		            if (nodes[nodes[jd].prev].size < cmax) {
 		              pushRight(nodes[jd].prev, nodes[jd].right);
 		              if (less(jd, nodes[jd].prev) ||
 		                  nodes[jd].item == nodes[pd].item) {
 		                nodes[nodes[jd].prev].prio = nodes[jd].prio;
 		                nodes[nodes[jd].prev].item = nodes[jd].item;
+		              }
 		              popRight(pd);
 		              deleteNode(jd);
 		              jd = pd;
 		            } else {
 		              int ld = nodes[nodes[jd].prev].right;
 		              popRight(nodes[jd].prev);
 		              pushLeft(jd, ld);
 		              if (less(ld, nodes[jd].right) ||
 		                  nodes[ld].item == nodes[pd].item) {
 		                nodes[jd].item = nodes[ld].item;
 		                nodes[jd].prio = nodes[ld].prio;
+		              }
 		              if (nodes[nodes[jd].prev].item == nodes[ld].item) {
 		                setPrio(nodes[jd].prev);
+		              }
 		              jd = nodes[jd].right;
+		            }
+		          }
 		        } else {
 		          jd = nodes[jd].right;
+		        }
+		      }
+		    }
 		    bool less(int id, int jd) const {
 		      return comp(nodes[id].prio, nodes[jd].prio);
+		    }
 		  public:
 		    /// \brief Returns true when the given class is alive.
 		    ///
 		    /// Returns true when the given class is alive, ie. the class is
 		    /// not nested into other class.
 		    bool alive(int cls) const {
 		      return classes[cls].parent < 0;
+		    }
 		    /// \brief Returns true when the given class is trivial.
 		    ///
 		    /// 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;
 		      nodes[id].right = -1;
 		      nodes[id].item = item;
 		      index[item] = id;
 		      int class_id = newClass();
 		      classes[class_id].parent = ~id;
 		      classes[class_id].depth = 0;
 		      classes[class_id].left = -1;
 		      classes[class_id].right = -1;
 		      if (first_class != -1) {
 		        classes[first_class].prev = class_id;
+		      }
 		      classes[class_id].next = first_class;
 		      classes[class_id].prev = -1;
 		      first_class = class_id;
 		      nodes[id].parent = ~class_id;
 		      return class_id;
+		    }
 		    /// \brief The class of the item.
 		    ///
 		    /// \return The alive class id of the item, which is not nested into
 		    /// other classes.
 		    ///
 		    /// The time complexity is O(log(n)).
 		    int find(const Item& item) const {
 		      return findClass(index[item]);
+		    }
 		    /// \brief Joins the classes.
 		    ///
 		    /// The current function joins the given classes. The parameter is
 		    /// an STL range which should be contains valid class ids. The
 		    /// time complexity is O(log(n)*k) where n is the overall number
 		    /// of the joined nodes and k is the number of classes.
 		    /// \return The class of the joined classes.
 		    /// \pre The range should contain at least two class ids.
 		    template <typename Iterator>
 		    int join(Iterator begin, Iterator end) {
 		      std::vector<int> cs;
 		      for (Iterator it = begin; it != end; ++it) {
 		        cs.push_back(*it);
+		      }
 		      int class_id = newClass();
 		      { // creation union-find
 		        if (first_class != -1) {
 		          classes[first_class].prev = class_id;
+		        }
 		        classes[class_id].next = first_class;
 		        classes[class_id].prev = -1;
 		        first_class = class_id;
 		        classes[class_id].depth = classes[cs[0]].depth;
 		        classes[class_id].parent = classes[cs[0]].parent;
 		        nodes[~(classes[class_id].parent)].parent = ~class_id;
 		        int l = cs[0];
 		        classes[class_id].left = l;
 		        classes[class_id].right = l;
 		        if (classes[l].next != -1) {
 		          classes[classes[l].next].prev = classes[l].prev;
+		        }
 		        classes[classes[l].prev].next = classes[l].next;
 		        classes[l].prev = -1;
 		        classes[l].next = -1;
 		        classes[l].depth = leftNode(l);
 		        classes[l].parent = class_id;
+		      }

0 comments (0 inline)

RhodeCode

Login to your account