lemon/max_matching.h
changeset 576 745e182d0139
parent 440 88ed40ad0d4f
child 581 aa1804409f29
equal deleted inserted replaced
4:e60683dec660 5:99828e8cc26c
    53   /// minus the number of barrier nodes is a lower bound on the
    53   /// minus the number of barrier nodes is a lower bound on the
    54   /// unmatched nodes, and the matching is optimal if and only if this bound is
    54   /// unmatched nodes, and the matching is optimal if and only if this bound is
    55   /// tight. This decomposition can be attained by calling \c
    55   /// tight. This decomposition can be attained by calling \c
    56   /// decomposition() after running the algorithm.
    56   /// decomposition() after running the algorithm.
    57   ///
    57   ///
    58   /// \param _Graph The graph type the algorithm runs on.
    58   /// \param GR The graph type the algorithm runs on.
    59   template <typename _Graph>
    59   template <typename GR>
    60   class MaxMatching {
    60   class MaxMatching {
    61   public:
    61   public:
    62 
    62 
    63     typedef _Graph Graph;
    63     typedef GR Graph;
    64     typedef typename Graph::template NodeMap<typename Graph::Arc>
    64     typedef typename Graph::template NodeMap<typename Graph::Arc>
    65     MatchingMap;
    65     MatchingMap;
    66 
    66 
    67     ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
    67     ///\brief Indicates the Gallai-Edmonds decomposition of the graph.
    68     ///
    68     ///
   461     /// \brief Initialize the matching from a map containing.
   461     /// \brief Initialize the matching from a map containing.
   462     ///
   462     ///
   463     /// Initialize the matching from a \c bool valued \c Edge map. This
   463     /// Initialize the matching from a \c bool valued \c Edge map. This
   464     /// map must have the property that there are no two incident edges
   464     /// map must have the property that there are no two incident edges
   465     /// with true value, ie. it contains a matching.
   465     /// with true value, ie. it contains a matching.
   466     /// \return %True if the map contains a matching.
   466     /// \return \c true if the map contains a matching.
   467     template <typename MatchingMap>
   467     template <typename MatchingMap>
   468     bool matchingInit(const MatchingMap& matching) {
   468     bool matchingInit(const MatchingMap& matching) {
   469       createStructures();
   469       createStructures();
   470 
   470 
   471       for (NodeIt n(_graph); n != INVALID; ++n) {
   471       for (NodeIt n(_graph); n != INVALID; ++n) {
   611   /// \brief Weighted matching in general graphs
   611   /// \brief Weighted matching in general graphs
   612   ///
   612   ///
   613   /// This class provides an efficient implementation of Edmond's
   613   /// This class provides an efficient implementation of Edmond's
   614   /// maximum weighted matching algorithm. The implementation is based
   614   /// maximum weighted matching algorithm. The implementation is based
   615   /// on extensive use of priority queues and provides
   615   /// on extensive use of priority queues and provides
   616   /// \f$O(nm\log(n))\f$ time complexity.
   616   /// \f$O(nm\log n)\f$ time complexity.
   617   ///
   617   ///
   618   /// The maximum weighted matching problem is to find undirected
   618   /// The maximum weighted matching problem is to find undirected
   619   /// edges in the graph with maximum overall weight and no two of
   619   /// edges in the graph with maximum overall weight and no two of
   620   /// them shares their ends. The problem can be formulated with the
   620   /// them shares their ends. The problem can be formulated with the
   621   /// following linear program.
   621   /// following linear program.
   645   /// solution can be get with \c nodeValue(), \c blossomNum() and \c
   645   /// solution can be get with \c nodeValue(), \c blossomNum() and \c
   646   /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
   646   /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
   647   /// "BlossomIt" nested class, which is able to iterate on the nodes
   647   /// "BlossomIt" nested class, which is able to iterate on the nodes
   648   /// of a blossom. If the value type is integral then the dual
   648   /// of a blossom. If the value type is integral then the dual
   649   /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
   649   /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
   650   template <typename _Graph,
   650   template <typename GR,
   651             typename _WeightMap = typename _Graph::template EdgeMap<int> >
   651             typename WM = typename GR::template EdgeMap<int> >
   652   class MaxWeightedMatching {
   652   class MaxWeightedMatching {
   653   public:
   653   public:
   654 
   654 
   655     typedef _Graph Graph;
   655     ///\e
   656     typedef _WeightMap WeightMap;
   656     typedef GR Graph;
       
   657     ///\e
       
   658     typedef WM WeightMap;
       
   659     ///\e
   657     typedef typename WeightMap::Value Value;
   660     typedef typename WeightMap::Value Value;
   658 
   661 
   659     /// \brief Scaling factor for dual solution
   662     /// \brief Scaling factor for dual solution
   660     ///
   663     ///
   661     /// Scaling factor for dual solution, it is equal to 4 or 1
   664     /// Scaling factor for dual solution, it is equal to 4 or 1
  1955   /// \brief Weighted perfect matching in general graphs
  1958   /// \brief Weighted perfect matching in general graphs
  1956   ///
  1959   ///
  1957   /// This class provides an efficient implementation of Edmond's
  1960   /// This class provides an efficient implementation of Edmond's
  1958   /// maximum weighted perfect matching algorithm. The implementation
  1961   /// maximum weighted perfect matching algorithm. The implementation
  1959   /// is based on extensive use of priority queues and provides
  1962   /// is based on extensive use of priority queues and provides
  1960   /// \f$O(nm\log(n))\f$ time complexity.
  1963   /// \f$O(nm\log n)\f$ time complexity.
  1961   ///
  1964   ///
  1962   /// The maximum weighted matching problem is to find undirected
  1965   /// The maximum weighted matching problem is to find undirected
  1963   /// edges in the graph with maximum overall weight and no two of
  1966   /// edges in the graph with maximum overall weight and no two of
  1964   /// them shares their ends and covers all nodes. The problem can be
  1967   /// them shares their ends and covers all nodes. The problem can be
  1965   /// formulated with the following linear program.
  1968   /// formulated with the following linear program.
  1988   /// solution can be get with \c nodeValue(), \c blossomNum() and \c
  1991   /// solution can be get with \c nodeValue(), \c blossomNum() and \c
  1989   /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
  1992   /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
  1990   /// "BlossomIt" nested class which is able to iterate on the nodes
  1993   /// "BlossomIt" nested class which is able to iterate on the nodes
  1991   /// of a blossom. If the value type is integral then the dual
  1994   /// of a blossom. If the value type is integral then the dual
  1992   /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
  1995   /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
  1993   template <typename _Graph,
  1996   template <typename GR,
  1994             typename _WeightMap = typename _Graph::template EdgeMap<int> >
  1997             typename WM = typename GR::template EdgeMap<int> >
  1995   class MaxWeightedPerfectMatching {
  1998   class MaxWeightedPerfectMatching {
  1996   public:
  1999   public:
  1997 
  2000 
  1998     typedef _Graph Graph;
  2001     typedef GR Graph;
  1999     typedef _WeightMap WeightMap;
  2002     typedef WM WeightMap;
  2000     typedef typename WeightMap::Value Value;
  2003     typedef typename WeightMap::Value Value;
  2001 
  2004 
  2002     /// \brief Scaling factor for dual solution
  2005     /// \brief Scaling factor for dual solution
  2003     ///
  2006     ///
  2004     /// Scaling factor for dual solution, it is equal to 4 or 1
  2007     /// Scaling factor for dual solution, it is equal to 4 or 1