RhodeCode

namespace lemon {

  /// \ingroup matching

  ///

  /// \brief Edmonds' alternating forest maximum matching algorithm.

  ///

  ///

  /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c

  /// MATCHED/C showing the Gallai-Edmonds decomposition of the

  /// graph. The nodes in \c EVEN/D induce a graph with

  /// factor-critical components, the nodes in \c ODD/A form the

  /// barrier, and the nodes in \c MATCHED/C induce a graph having a

  /// minus the number of barrier nodes is a lower bound on the

  /// tight. This decomposition can be attained by calling \c

  /// decomposition() after running the algorithm.

  ///

  /// \param _Graph The graph type the algorithm runs on.

  template <typename _Graph>

  class MaxMatching {

    typedef _Graph Graph;

    typedef typename Graph::template NodeMap<typename Graph::Arc>

    MatchingMap;

    ///\brief Indicates the Gallai-Edmonds decomposition of the graph.

    ///

    ///nodes with Status \c EVEN/D induce a graph with factor-critical

    ///components, the nodes in \c ODD/A form the canonical barrier,

    ///and the nodes in \c MATCHED/C induce a graph having a perfect

    ///matching.

    enum Status {

      EVEN = 1, D = 1, MATCHED = 0, C = 0, ODD = -1, A = -1, UNMATCHED = -2

    ~MaxMatching() {

      destroyStructures();

    }

    /// \name Execution control

    /// \c run() member function.

    /// \n

    /// \ref init(), \ref greedyInit() or \ref matchingInit()

    /// startParse() or startDense() functions.

    ///@{

    /// \brief Sets the actual matching to the empty matching.

    ///

      for(NodeIt n(_graph); n != INVALID; ++n) {

        _matching->set(n, INVALID);

        _status->set(n, UNMATCHED);

      }

    }

    ///

    void greedyInit() {

      createStructures();

      for (NodeIt n(_graph); n != INVALID; ++n) {

        _matching->set(n, INVALID);

        _status->set(n, UNMATCHED);

      }

          }

        }

      }

    }

    ///

    /// Initialize the matching from a \c bool valued \c Edge map. This

    /// map must have the property that there are no two incident edges

    /// with true value, ie. it contains a matching.

    /// \return %True if the map contains a matching.

    template <typename MatchingMap>

      }

    }

    /// \brief Starts Edmonds' algorithm.

    ///

    /// It runs Edmonds' algorithm with a heuristic of postponing

    void startDense() {

      for(NodeIt n(_graph); n != INVALID; ++n) {

        if ((*_status)[n] == UNMATCHED) {

          (*_blossom_rep)[_blossom_set->insert(n)] = n;

          _tree_set->insert(n);

          _status->set(n, EVEN);

      }

    }

    /// @}

    /// \name Primal solution

    /// @{

    ///

    ///run() it returns the size of the maximum matching in the graph.

    int matchingSize() const {

      int size = 0;

      for (NodeIt n(_graph); n != INVALID; ++n) {

        if ((*_matching)[n] != INVALID) {

          ++size;

        _graph.target((*_matching)[n]) : INVALID;

    }

    /// @}

    /// \name Dual solution

    /// @{

    /// \brief Returns the class of the node in the Edmonds-Gallai

    /// decomposition.

    ///

  ///

  /// The algorithm can be executed with \c run() or the \c init() and

  /// then the \c start() member functions. After it the matching can

  /// be asked with \c matching() or mate() functions. The dual

  /// solution can be get with \c nodeValue(), \c blossomNum() and \c

  /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt

  /// of a blossom. If the value type is integral then the dual

  /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".

  template <typename _Graph,

            typename _WeightMap = typename _Graph::template EdgeMap<int> >

  class MaxWeightedMatching {

  public:

    ~MaxWeightedMatching() {

      destroyStructures();

    }

    /// \name Execution control

    /// \c run() member function.

    ///@{

    /// \brief Initialize the algorithm

    ///

      start();

    }

    /// @}

    /// \name Primal solution

    /// @{

    ///

    Value matchingValue() const {

      Value sum = 0;

      for (NodeIt n(_graph); n != INVALID; ++n) {

        if ((*_matching)[n] != INVALID) {

          sum += _weight[(*_matching)[n]];

        }

        _graph.target((*_matching)[node]) : INVALID;

    }

    /// @}

    /// \name Dual solution

    /// @{

    /// \brief Returns the value of the dual solution.

    ///

    /// Returns the value of the dual solution. It should be equal to

    /// Returns the the value of the blossom.

    /// \see BlossomIt

    Value blossomValue(int k) const {

      return _blossom_potential[k].value;

    }

    ///

    /// subset of the nodes.

    class BlossomIt {

    public:

      /// \brief Constructor.

      ///

      BlossomIt(const MaxWeightedMatching& algorithm, int variable)

        : _algorithm(&algorithm)

      {

        _index = _algorithm->_blossom_potential[variable].begin;

        _last = _algorithm->_blossom_potential[variable].end;

      }

    ~MaxWeightedPerfectMatching() {

      destroyStructures();

    }

    /// \name Execution control

    /// \c run() member function.

    ///@{

    /// \brief Initialize the algorithm

    ///

      return start();

    }

    /// @}

    /// \name Primal solution

    /// @{

    /// \brief Returns the matching value.

    ///

    /// Returns the matching value.

      return _graph.target((*_matching)[node]);

    }

    /// @}

    /// \name Dual solution

    /// @{

    /// \brief Returns the value of the dual solution.

    ///

    /// Returns the value of the dual solution. It should be equal to

    /// Returns the the value of the blossom.

    /// \see BlossomIt

    Value blossomValue(int k) const {

      return _blossom_potential[k].value;

    }

    ///

    /// subset of the nodes.

    class BlossomIt {

    public:

      /// \brief Constructor.

      ///

      BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)

        : _algorithm(&algorithm)

      {

        _index = _algorithm->_blossom_potential[variable].begin;

        _last = _algorithm->_blossom_potential[variable].end;

      }