lemon/max_matching.h
changeset 415 4b6112235fad
parent 327 91d63b8b1a4c
child 425 cace3206223b
equal deleted inserted replaced
1:8907e8eb252e 2:a95ea2463839
    37 
    37 
    38   /// \ingroup matching
    38   /// \ingroup matching
    39   ///
    39   ///
    40   /// \brief Edmonds' alternating forest maximum matching algorithm.
    40   /// \brief Edmonds' alternating forest maximum matching algorithm.
    41   ///
    41   ///
    42   /// This class provides Edmonds' alternating forest matching
    42   /// This class implements Edmonds' alternating forest matching
    43   /// algorithm. The starting matching (if any) can be passed to the
    43   /// algorithm. The algorithm can be started from an arbitrary initial
    44   /// algorithm using some of init functions.
    44   /// matching (the default is the empty one)
    45   ///
    45   ///
    46   /// The dual side of a matching is a map of the nodes to
    46   /// The dual solution of the problem is a map of the nodes to
    47   /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
    47   /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c
    48   /// MATCHED/C showing the Gallai-Edmonds decomposition of the
    48   /// MATCHED/C showing the Gallai-Edmonds decomposition of the
    49   /// graph. The nodes in \c EVEN/D induce a graph with
    49   /// graph. The nodes in \c EVEN/D induce a graph with
    50   /// factor-critical components, the nodes in \c ODD/A form the
    50   /// factor-critical components, the nodes in \c ODD/A form the
    51   /// barrier, and the nodes in \c MATCHED/C induce a graph having a
    51   /// barrier, and the nodes in \c MATCHED/C induce a graph having a
    52   /// perfect matching. The number of the fractor critical components
    52   /// perfect matching. The number of the factor-critical components
    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 if the matching is optimal 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 _Graph The graph type the algorithm runs on.
    59   template <typename _Graph>
    59   template <typename _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     ///
    69     ///Indicates the Gallai-Edmonds decomposition of the graph, which
    69     ///Indicates the Gallai-Edmonds decomposition of the graph. The
    70     ///shows an upper bound on the size of a maximum matching. The
       
    71     ///nodes with Status \c EVEN/D induce a graph with factor-critical
    70     ///nodes with Status \c EVEN/D induce a graph with factor-critical
    72     ///components, the nodes in \c ODD/A form the canonical barrier,
    71     ///components, the nodes in \c ODD/A form the canonical barrier,
    73     ///and the nodes in \c MATCHED/C induce a graph having a perfect
    72     ///and the nodes in \c MATCHED/C induce a graph having a perfect
    74     ///matching.
    73     ///matching.
    75     enum Status {
    74     enum Status {
   408     ~MaxMatching() {
   407     ~MaxMatching() {
   409       destroyStructures();
   408       destroyStructures();
   410     }
   409     }
   411 
   410 
   412     /// \name Execution control
   411     /// \name Execution control
   413     /// The simplest way to execute the algorithm is to use the member
   412     /// The simplest way to execute the algorithm is to use the
   414     /// \c run() member function.
   413     /// \c run() member function.
   415     /// \n
   414     /// \n
   416 
   415 
   417     /// If you need more control on the execution, first you must call
   416     /// If you need better control on the execution, you must call
   418     /// \ref init(), \ref greedyInit() or \ref matchingInit()
   417     /// \ref init(), \ref greedyInit() or \ref matchingInit()
   419     /// functions, then you can start the algorithm with the \ref
   418     /// functions first, then you can start the algorithm with the \ref
   420     /// startParse() or startDense() functions.
   419     /// startParse() or startDense() functions.
   421 
   420 
   422     ///@{
   421     ///@{
   423 
   422 
   424     /// \brief Sets the actual matching to the empty matching.
   423     /// \brief Sets the actual matching to the empty matching.
   431         _matching->set(n, INVALID);
   430         _matching->set(n, INVALID);
   432         _status->set(n, UNMATCHED);
   431         _status->set(n, UNMATCHED);
   433       }
   432       }
   434     }
   433     }
   435 
   434 
   436     ///\brief Finds a greedy matching for initial matching.
   435     ///\brief Finds an initial matching in a greedy way
   437     ///
   436     ///
   438     ///For initial matchig it finds a maximal greedy matching.
   437     ///It finds an initial matching in a greedy way.
   439     void greedyInit() {
   438     void greedyInit() {
   440       createStructures();
   439       createStructures();
   441       for (NodeIt n(_graph); n != INVALID; ++n) {
   440       for (NodeIt n(_graph); n != INVALID; ++n) {
   442         _matching->set(n, INVALID);
   441         _matching->set(n, INVALID);
   443         _status->set(n, UNMATCHED);
   442         _status->set(n, UNMATCHED);
   457         }
   456         }
   458       }
   457       }
   459     }
   458     }
   460 
   459 
   461 
   460 
   462     /// \brief Initialize the matching from the map containing a matching.
   461     /// \brief Initialize the matching from a map containing.
   463     ///
   462     ///
   464     /// 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
   465     /// 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
   466     /// with true value, ie. it contains a matching.
   465     /// with true value, ie. it contains a matching.
   467     /// \return %True if the map contains a matching.
   466     /// \return %True if the map contains a matching.
   505     }
   504     }
   506 
   505 
   507     /// \brief Starts Edmonds' algorithm.
   506     /// \brief Starts Edmonds' algorithm.
   508     ///
   507     ///
   509     /// It runs Edmonds' algorithm with a heuristic of postponing
   508     /// It runs Edmonds' algorithm with a heuristic of postponing
   510     /// shrinks, giving a faster algorithm for dense graphs.
   509     /// shrinks, therefore resulting in a faster algorithm for dense graphs.
   511     void startDense() {
   510     void startDense() {
   512       for(NodeIt n(_graph); n != INVALID; ++n) {
   511       for(NodeIt n(_graph); n != INVALID; ++n) {
   513         if ((*_status)[n] == UNMATCHED) {
   512         if ((*_status)[n] == UNMATCHED) {
   514           (*_blossom_rep)[_blossom_set->insert(n)] = n;
   513           (*_blossom_rep)[_blossom_set->insert(n)] = n;
   515           _tree_set->insert(n);
   514           _tree_set->insert(n);
   536     }
   535     }
   537 
   536 
   538     /// @}
   537     /// @}
   539 
   538 
   540     /// \name Primal solution
   539     /// \name Primal solution
   541     /// Functions for get the primal solution, ie. the matching.
   540     /// Functions to get the primal solution, ie. the matching.
   542 
   541 
   543     /// @{
   542     /// @{
   544 
   543 
   545     ///\brief Returns the size of the actual matching stored.
   544     ///\brief Returns the size of the current matching.
   546     ///
   545     ///
   547     ///Returns the size of the actual matching stored. After \ref
   546     ///Returns the size of the current matching. After \ref
   548     ///run() it returns the size of the maximum matching in the graph.
   547     ///run() it returns the size of the maximum matching in the graph.
   549     int matchingSize() const {
   548     int matchingSize() const {
   550       int size = 0;
   549       int size = 0;
   551       for (NodeIt n(_graph); n != INVALID; ++n) {
   550       for (NodeIt n(_graph); n != INVALID; ++n) {
   552         if ((*_matching)[n] != INVALID) {
   551         if ((*_matching)[n] != INVALID) {
   581     }
   580     }
   582 
   581 
   583     /// @}
   582     /// @}
   584 
   583 
   585     /// \name Dual solution
   584     /// \name Dual solution
   586     /// Functions for get the dual solution, ie. the decomposition.
   585     /// Functions to get the dual solution, ie. the decomposition.
   587 
   586 
   588     /// @{
   587     /// @{
   589 
   588 
   590     /// \brief Returns the class of the node in the Edmonds-Gallai
   589     /// \brief Returns the class of the node in the Edmonds-Gallai
   591     /// decomposition.
   590     /// decomposition.
   643   /// The algorithm can be executed with \c run() or the \c init() and
   642   /// The algorithm can be executed with \c run() or the \c init() and
   644   /// then the \c start() member functions. After it the matching can
   643   /// then the \c start() member functions. After it the matching can
   645   /// be asked with \c matching() or mate() functions. The dual
   644   /// be asked with \c matching() or mate() functions. The dual
   646   /// solution can be get with \c nodeValue(), \c blossomNum() and \c
   645   /// solution can be get with \c nodeValue(), \c blossomNum() and \c
   647   /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
   646   /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt
   648   /// "BlossomIt" nested class which is able to iterate on the nodes
   647   /// "BlossomIt" nested class, which is able to iterate on the nodes
   649   /// 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
   650   /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
   649   /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4".
   651   template <typename _Graph,
   650   template <typename _Graph,
   652             typename _WeightMap = typename _Graph::template EdgeMap<int> >
   651             typename _WeightMap = typename _Graph::template EdgeMap<int> >
   653   class MaxWeightedMatching {
   652   class MaxWeightedMatching {
  1628     ~MaxWeightedMatching() {
  1627     ~MaxWeightedMatching() {
  1629       destroyStructures();
  1628       destroyStructures();
  1630     }
  1629     }
  1631 
  1630 
  1632     /// \name Execution control
  1631     /// \name Execution control
  1633     /// The simplest way to execute the algorithm is to use the member
  1632     /// The simplest way to execute the algorithm is to use the
  1634     /// \c run() member function.
  1633     /// \c run() member function.
  1635 
  1634 
  1636     ///@{
  1635     ///@{
  1637 
  1636 
  1638     /// \brief Initialize the algorithm
  1637     /// \brief Initialize the algorithm
  1789     }
  1788     }
  1790 
  1789 
  1791     /// @}
  1790     /// @}
  1792 
  1791 
  1793     /// \name Primal solution
  1792     /// \name Primal solution
  1794     /// Functions for get the primal solution, ie. the matching.
  1793     /// Functions to get the primal solution, ie. the matching.
  1795 
  1794 
  1796     /// @{
  1795     /// @{
  1797 
  1796 
  1798     /// \brief Returns the matching value.
  1797     /// \brief Returns the weight of the matching.
  1799     ///
  1798     ///
  1800     /// Returns the matching value.
  1799     /// Returns the weight of the matching.
  1801     Value matchingValue() const {
  1800     Value matchingValue() const {
  1802       Value sum = 0;
  1801       Value sum = 0;
  1803       for (NodeIt n(_graph); n != INVALID; ++n) {
  1802       for (NodeIt n(_graph); n != INVALID; ++n) {
  1804         if ((*_matching)[n] != INVALID) {
  1803         if ((*_matching)[n] != INVALID) {
  1805           sum += _weight[(*_matching)[n]];
  1804           sum += _weight[(*_matching)[n]];
  1846     }
  1845     }
  1847 
  1846 
  1848     /// @}
  1847     /// @}
  1849 
  1848 
  1850     /// \name Dual solution
  1849     /// \name Dual solution
  1851     /// Functions for get the dual solution.
  1850     /// Functions to get the dual solution.
  1852 
  1851 
  1853     /// @{
  1852     /// @{
  1854 
  1853 
  1855     /// \brief Returns the value of the dual solution.
  1854     /// \brief Returns the value of the dual solution.
  1856     ///
  1855     ///
  1896     /// \see BlossomIt
  1895     /// \see BlossomIt
  1897     Value blossomValue(int k) const {
  1896     Value blossomValue(int k) const {
  1898       return _blossom_potential[k].value;
  1897       return _blossom_potential[k].value;
  1899     }
  1898     }
  1900 
  1899 
  1901     /// \brief Lemon iterator for get the items of the blossom.
  1900     /// \brief Iterator for obtaining the nodes of the blossom.
  1902     ///
  1901     ///
  1903     /// Lemon iterator for get the nodes of the blossom. This class
  1902     /// Iterator for obtaining the nodes of the blossom. This class
  1904     /// provides a common style lemon iterator which gives back a
  1903     /// provides a common lemon style iterator for listing a
  1905     /// subset of the nodes.
  1904     /// subset of the nodes.
  1906     class BlossomIt {
  1905     class BlossomIt {
  1907     public:
  1906     public:
  1908 
  1907 
  1909       /// \brief Constructor.
  1908       /// \brief Constructor.
  1910       ///
  1909       ///
  1911       /// Constructor for get the nodes of the variable.
  1910       /// Constructor to get the nodes of the variable.
  1912       BlossomIt(const MaxWeightedMatching& algorithm, int variable)
  1911       BlossomIt(const MaxWeightedMatching& algorithm, int variable)
  1913         : _algorithm(&algorithm)
  1912         : _algorithm(&algorithm)
  1914       {
  1913       {
  1915         _index = _algorithm->_blossom_potential[variable].begin;
  1914         _index = _algorithm->_blossom_potential[variable].begin;
  1916         _last = _algorithm->_blossom_potential[variable].end;
  1915         _last = _algorithm->_blossom_potential[variable].end;
  2815     ~MaxWeightedPerfectMatching() {
  2814     ~MaxWeightedPerfectMatching() {
  2816       destroyStructures();
  2815       destroyStructures();
  2817     }
  2816     }
  2818 
  2817 
  2819     /// \name Execution control
  2818     /// \name Execution control
  2820     /// The simplest way to execute the algorithm is to use the member
  2819     /// The simplest way to execute the algorithm is to use the
  2821     /// \c run() member function.
  2820     /// \c run() member function.
  2822 
  2821 
  2823     ///@{
  2822     ///@{
  2824 
  2823 
  2825     /// \brief Initialize the algorithm
  2824     /// \brief Initialize the algorithm
  2953     }
  2952     }
  2954 
  2953 
  2955     /// @}
  2954     /// @}
  2956 
  2955 
  2957     /// \name Primal solution
  2956     /// \name Primal solution
  2958     /// Functions for get the primal solution, ie. the matching.
  2957     /// Functions to get the primal solution, ie. the matching.
  2959 
  2958 
  2960     /// @{
  2959     /// @{
  2961 
  2960 
  2962     /// \brief Returns the matching value.
  2961     /// \brief Returns the matching value.
  2963     ///
  2962     ///
  2994     }
  2993     }
  2995 
  2994 
  2996     /// @}
  2995     /// @}
  2997 
  2996 
  2998     /// \name Dual solution
  2997     /// \name Dual solution
  2999     /// Functions for get the dual solution.
  2998     /// Functions to get the dual solution.
  3000 
  2999 
  3001     /// @{
  3000     /// @{
  3002 
  3001 
  3003     /// \brief Returns the value of the dual solution.
  3002     /// \brief Returns the value of the dual solution.
  3004     ///
  3003     ///
  3044     /// \see BlossomIt
  3043     /// \see BlossomIt
  3045     Value blossomValue(int k) const {
  3044     Value blossomValue(int k) const {
  3046       return _blossom_potential[k].value;
  3045       return _blossom_potential[k].value;
  3047     }
  3046     }
  3048 
  3047 
  3049     /// \brief Lemon iterator for get the items of the blossom.
  3048     /// \brief Iterator for obtaining the nodes of the blossom.
  3050     ///
  3049     ///
  3051     /// Lemon iterator for get the nodes of the blossom. This class
  3050     /// Iterator for obtaining the nodes of the blossom. This class
  3052     /// provides a common style lemon iterator which gives back a
  3051     /// provides a common lemon style iterator for listing a
  3053     /// subset of the nodes.
  3052     /// subset of the nodes.
  3054     class BlossomIt {
  3053     class BlossomIt {
  3055     public:
  3054     public:
  3056 
  3055 
  3057       /// \brief Constructor.
  3056       /// \brief Constructor.
  3058       ///
  3057       ///
  3059       /// Constructor for get the nodes of the variable.
  3058       /// Constructor to get the nodes of the variable.
  3060       BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
  3059       BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable)
  3061         : _algorithm(&algorithm)
  3060         : _algorithm(&algorithm)
  3062       {
  3061       {
  3063         _index = _algorithm->_blossom_potential[variable].begin;
  3062         _index = _algorithm->_blossom_potential[variable].begin;
  3064         _last = _algorithm->_blossom_potential[variable].end;
  3063         _last = _algorithm->_blossom_potential[variable].end;