RhodeCode

  ///

  /// The algorithm calculates an optimal fractional matching and a

  /// barrier. The number of adjacents of any node set minus the size

  /// of node set is a lower bound on the uncovered nodes in the

  /// graph. For maximum matching a barrier is computed which

  /// maximizes this difference.

  ///

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

  /// the matching (the primal solution) and the barrier (the dual

  /// solution) can be obtained using the query functions.

  ///

  /// The primal solution is multiplied by

  ///

  /// \tparam GR The undirected graph type the algorithm runs on.

#ifdef DOXYGEN

  template <typename GR, typename TR>

#else

  template <typename GR,

            typename TR = MaxFractionalMatchingDefaultTraits<GR> >

#endif

  class MaxFractionalMatching {

  public:

    /// \brief The \ref MaxFractionalMatchingDefaultTraits "traits

      return (*_level)[node] >= _empty_level;

    }

    /// @}

  };

  /// \ingroup matching

  ///

  /// \brief Weighted fractional matching in general graphs

  ///

  /// This class provides an efficient implementation of fractional

  ///

  /// The maximum weighted fractional matching is a relaxation of the

  /// maximum weighted matching problem where the odd set constraints

  /// are omitted.

  /// It can be formulated with the following linear program.

  /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f]

  /// \f[x_e \ge 0\quad \forall e\in E\f]

  /// \f[\max \sum_{e\in E}x_ew_e\f]

  /// where \f$\delta(X)\f$ is the set of edges incident to a node in

  /// \f$X\f$. The result must be the union of a matching with one

  /// value edges and a set of odd length cycles with half value edges.

  ///

  /// The algorithm calculates an optimal fractional matching and a

  /// proof of the optimality. The solution of the dual problem can be

  /// used to check the result of the algorithm. The dual linear

  /// problem is the following.

  /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]

  /// \f[y_u \ge 0 \quad \forall u \in V\f]

  ///

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

  /// After it the matching (the primal solution) and the dual solution

  /// can be obtained using the query functions.

  ///

  /// If the value type is integer, then the primal and the dual

  /// solutions are multiplied by

  ///

  /// \tparam GR The undirected graph type the algorithm runs on.

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

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename WM>

#else

  template <typename GR,

            typename WM = typename GR::template EdgeMap<int> >

#endif

  class MaxWeightedFractionalMatching {

  public:

              --unmatched;

            } else {

              augmentOnEdge(e);

              unmatched -= 2;

            }

          } break;

        }

      }

    }

    /// \brief Run the algorithm.

    ///

    ///

    /// \note mwfm.run() is just a shortcut of the following code.

    /// \code

    ///   mwfm.init();

    ///   mwfm.start();

    /// \endcode

    void run() {

      init();

      start();

    }

    /// @}

      return (*_node_potential)[n];

    }

    /// @}

  };

  /// \ingroup matching

  ///

  /// \brief Weighted fractional perfect matching in general graphs

  ///

  /// This class provides an efficient implementation of fractional

  ///

  /// The maximum weighted fractional perfect matching is a relaxation

  /// of the maximum weighted perfect matching problem where the odd

  /// set constraints are omitted.

  /// It can be formulated with the following linear program.

  /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f]

  /// \f[x_e \ge 0\quad \forall e\in E\f]

  /// \f[\max \sum_{e\in E}x_ew_e\f]

  /// where \f$\delta(X)\f$ is the set of edges incident to a node in

  /// \f$X\f$. The result must be the union of a matching with one

  /// value edges and a set of odd length cycles with half value edges.

  ///

  /// The algorithm calculates an optimal fractional matching and a

  /// proof of the optimality. The solution of the dual problem can be

  /// used to check the result of the algorithm. The dual linear

  /// problem is the following.

  /// \f[ y_u + y_v \ge w_{uv} \quad \forall uv\in E\f]

  ///

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

  /// After it the matching (the primal solution) and the dual solution

  /// can be obtained using the query functions.

  /// If the value type is integer, then the primal and the dual

  /// solutions are multiplied by

  ///

  /// \tparam GR The undirected graph type the algorithm runs on.

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

  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>".

#ifdef DOXYGEN

  template <typename GR, typename WM>

#else

  template <typename GR,

            typename WM = typename GR::template EdgeMap<int> >

#endif

  class MaxWeightedPerfectFractionalMatching {

  public:

            } else {

              augmentOnEdge(e);

              unmatched -= 2;

            }

          } break;

        }

      }

      return true;

    }

    /// \brief Run the algorithm.

    ///

    ///

    /// \note mwfm.run() is just a shortcut of the following code.

    /// \code

    ///   mwpfm.init();

    ///   mwpfm.start();

    /// \endcode

    bool run() {

      init();

      return start();

    }

    /// @}