RhodeCode

#ifndef LEMON_MAX_MATCHING_H

#define LEMON_MAX_MATCHING_H

  /// It can be started from an arbitrary initial matching 

    ///These constants are used for indicating the Gallai-Edmonds 

    ///with status \c MATCHED (or \c C) induce a subgraph having a 

    /// \brief Start Edmonds' algorithm with a heuristic improvement 

    /// This function runs Edmonds' algorithm. An additional heuristic of 

    /// postponing shrinks is used for relatively dense graphs 

    /// This function returns the size (cardinality) of the current matching. 

    /// This function returns \c true if the given edge is in the current 

    /// given node in the current matching or \c INVALID if the node is 

    /// This function returns the mate of the given node in the current 

    /// Functions to get the dual solution, i.e. the Gallai-Edmonds 

  /// The maximum weighted matching problem is to find a subset of the 

  /// edges in an undirected graph with maximum overall weight for which 

  /// The algorithm can be executed with the run() function. 

  /// can be obtained using the query functions and the 

  /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, 

  /// which is able to iterate on the nodes of a blossom. 

  /// \tparam WM The type edge weight map. The default type is 

      EVEN = -1, MATCHED = 0, ODD = 1, UNMATCHED = -2

      _node_num = countNodes(_graph);

      _blossom_num = _node_num * 3 / 2;

          } else if ((*_blossom_data)[vb].status == UNMATCHED) {

            if (_delta3->state(e) != _delta3->IN_HEAP) {

              _delta3->push(e, rw);

            }

                           (*_blossom_data)[vb].offset){

                  _delta2->decrease(vb, _blossom_set->classPrio(vb) -

                                   (*_blossom_data)[vb].offset);

                }

              }

            }

          }

        }

      }

      (*_blossom_data)[blossom].offset = 0;

    }

    void matchedToOdd(int blossom) {

      if (_delta2->state(blossom) == _delta2->IN_HEAP) {

        _delta2->erase(blossom);

      }

      (*_blossom_data)[blossom].offset += _delta_sum;

      if (!_blossom_set->trivial(blossom)) {

        _delta4->push(blossom, (*_blossom_data)[blossom].pot / 2 +

                     (*_blossom_data)[blossom].offset);

      }

    }

    void evenToMatched(int blossom, int tree) {

      if (!_blossom_set->trivial(blossom)) {

        (*_blossom_data)[blossom].pot += 2 * _delta_sum;

      }

      for (typename BlossomSet::ItemIt n(*_blossom_set, blossom);

           n != INVALID; ++n) {

        int ni = (*_node_index)[n];

        (*_node_data)[ni].pot -= _delta_sum;

        _delta1->erase(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);

            if (vt != tree) {

              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);

            }

          } else {

            typename std::map<int, Arc>::iterator it =

              (*_node_data)[vi].heap_index.find(tree);

            if (it != (*_node_data)[vi].heap_index.end()) {

              (*_node_data)[vi].heap.erase(it->second);

              (*_node_data)[vi].heap_index.erase(it);

              if ((*_node_data)[vi].heap.empty()) {

                _blossom_set->increase(v, std::numeric_limits<Value>::max());

              } else if ((*_blossom_set)[v] < (*_node_data)[vi].heap.prio()) {

                _blossom_set->increase(v, (*_node_data)[vi].heap.prio());

              }

              if ((*_blossom_data)[vb].status == MATCHED) {

                if (_blossom_set->classPrio(vb) ==

                    std::numeric_limits<Value>::max()) {

                  _delta2->erase(vb);

                } else if ((*_delta2)[vb] < _blossom_set->classPrio(vb) -

                           (*_blossom_data)[vb].offset) {

                  _delta2->increase(vb, _blossom_set->classPrio(vb) -

                                   (*_blossom_data)[vb].offset);

                }

              }

            }

          }

        }

      }

    }

    void oddToMatched(int blossom) {

      (*_blossom_data)[blossom].offset -= _delta_sum;

      if (_blossom_set->classPrio(blossom) !=

          std::numeric_limits<Value>::max()) {

        _delta2->push(blossom, _blossom_set->classPrio(blossom) -

                       (*_blossom_data)[blossom].offset);

      }

      if (!_blossom_set->trivial(blossom)) {

        _delta4->erase(blossom);

      }

    }

    void oddToEven(int blossom, int tree) {

      if (!_blossom_set->trivial(blossom)) {

        _delta4->erase(blossom);

        (*_blossom_data)[blossom].pot -=

          2 * (2 * _delta_sum - (*_blossom_data)[blossom].offset);

      }

      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();

        (*_node_data)[ni].pot +=

          2 * _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;

              }

            } 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) {

                  _delta2->push(vb, _blossom_set->classPrio(vb) -

                               (*_blossom_data)[vb].offset);

                } else if ((*_delta2)[vb] > _blossom_set->classPrio(vb) -

    void matchedToUnmatched(int blossom) {

        _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);

          if ((*_blossom_data)[vb].status == EVEN) {

            if (_delta3->state(e) != _delta3->IN_HEAP) {

              _delta3->push(e, rw);

    void unmatchedToMatched(int blossom) {

          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);

              (*_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;

              (*_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);

            }

      (*_blossom_data)[blossom].status = UNMATCHED;

      matchedToUnmatched(blossom);

      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);

      }

                           _graph.oppositeArc((*_blossom_data)[tb].next);

        if ((*_blossom_data)[blossoms[i]].status == MATCHED) {

        _delta_sum = d1; OpType ot = D1;

        if (d3 < _delta_sum) { _delta_sum = d3; ot = D3; }

            Arc e = (*_node_data)[(*_node_index)[n]].heap.top();

            extendOnArc(e);

              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;

              }

    /// Functions to get the primal solution, i.e. the maximum weighted 

      return sum /= 2;

    /// This function returns \c true if the given edge is in the found 

    /// given node in the found matching or \c INVALID if the node is 

    /// This function returns the mate of the given node in the found 

    /// This function returns the value of the dual solution. 

    /// It should be equal to the primal value scaled by \ref dualScale 

    /// This class provides an iterator for obtaining the nodes of the 

    /// Before using this iterator, you must allocate a 

      /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or 

      /// \ref MaxWeightedMatching::start() "algorithm.start()" must be 

  /// The maximum weighted perfect matching problem is to find a subset of 

  /// the edges in an undirected graph with maximum overall weight for which 

  /// The algorithm can be executed with the run() function. 

  /// can be obtained using the query functions and the 

  /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, 

  /// which is able to iterate on the nodes of a blossom. 

  /// \tparam WM The type edge weight map. The default type is 

      _node_num = countNodes(_graph);

      _blossom_num = _node_num * 3 / 2;

        _delta_sum = d2; OpType ot = D2;

        if (d3 < _delta_sum) { _delta_sum = d3; ot = D3; }

    /// Functions to get the primal solution, i.e. the maximum weighted 

      return sum /= 2;

    /// This function returns \c true if the given edge is in the found 

    /// given node in the found matching or \c INVALID if the node is 

    /// This function returns the mate of the given node in the found 

    /// This function returns the value of the dual solution. 

    /// It should be equal to the primal value scaled by \ref dualScale 

    /// This class provides an iterator for obtaining the nodes of the 

    /// Before using this iterator, you must allocate a 

      /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" 

      /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" 

#endif //LEMON_MAX_MATCHING_H