Changeset 330:5ba887b7def4 in lemon-main
- Timestamp:
- 10/22/08 14:53:34 (16 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
-
lemon/max_matching.h (modified) (20 diffs)
Legend:
- Unmodified
- Added
- Removed
-
lemon/max_matching.h
r327 r330 40 40 /// \brief Edmonds' alternating forest maximum matching algorithm. 41 41 /// 42 /// This class provides Edmonds' alternating forest matching43 /// algorithm. The starting matching (if any) can be passed to the44 /// algorithm using some of init functions.42 /// This class implements Edmonds' alternating forest matching 43 /// algorithm. The algorithm can be started from an arbitrary initial 44 /// matching (the default is the empty one) 45 45 /// 46 /// The dual s ide of a matchingis a map of the nodes to46 /// The dual solution of the problem is a map of the nodes to 47 47 /// MaxMatching::Status, having values \c EVEN/D, \c ODD/A and \c 48 48 /// MATCHED/C showing the Gallai-Edmonds decomposition of the … … 50 50 /// factor-critical components, the nodes in \c ODD/A form the 51 51 /// barrier, and the nodes in \c MATCHED/C induce a graph having a 52 /// perfect matching. The number of the f ractorcritical components52 /// perfect matching. The number of the factor-critical components 53 53 /// minus the number of barrier nodes is a lower bound on the 54 /// unmatched nodes, and if the matching is optimalthis bound is54 /// unmatched nodes, and the matching is optimal if and only if this bound is 55 55 /// tight. This decomposition can be attained by calling \c 56 56 /// decomposition() after running the algorithm. … … 67 67 ///\brief Indicates the Gallai-Edmonds decomposition of the graph. 68 68 /// 69 ///Indicates the Gallai-Edmonds decomposition of the graph, which 70 ///shows an upper bound on the size of a maximum matching. The 69 ///Indicates the Gallai-Edmonds decomposition of the graph. The 71 70 ///nodes with Status \c EVEN/D induce a graph with factor-critical 72 71 ///components, the nodes in \c ODD/A form the canonical barrier, … … 411 410 412 411 /// \name Execution control 413 /// The simplest way to execute the algorithm is to use the member412 /// The simplest way to execute the algorithm is to use the 414 413 /// \c run() member function. 415 414 /// \n 416 415 417 /// If you need more control on the execution, firstyou must call416 /// If you need better control on the execution, you must call 418 417 /// \ref init(), \ref greedyInit() or \ref matchingInit() 419 /// functions , then you can start the algorithm with the \ref418 /// functions first, then you can start the algorithm with the \ref 420 419 /// startParse() or startDense() functions. 421 420 … … 434 433 } 435 434 436 ///\brief Finds a greedy matching for initial matching.437 /// 438 /// For initial matchig it finds a maximal greedy matching.435 ///\brief Finds an initial matching in a greedy way 436 /// 437 ///It finds an initial matching in a greedy way. 439 438 void greedyInit() { 440 439 createStructures(); … … 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 463 /// Initialize the matching from a \c bool valued \c Edge map. This … … 508 507 /// 509 508 /// It runs Edmonds' algorithm with a heuristic of postponing 510 /// shrinks, givinga faster algorithm for dense graphs.509 /// shrinks, therefore resulting in a faster algorithm for dense graphs. 511 510 void startDense() { 512 511 for(NodeIt n(_graph); n != INVALID; ++n) { … … 539 538 540 539 /// \name Primal solution 541 /// Functions forget 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.546 /// 547 ///Returns the size of the actual matching stored. After \ref544 ///\brief Returns the size of the current matching. 545 /// 546 ///Returns the size of the current matching. After \ref 548 547 ///run() it returns the size of the maximum matching in the graph. 549 548 int matchingSize() const { … … 584 583 585 584 /// \name Dual solution 586 /// Functions forget the dual solution, ie. the decomposition.585 /// Functions to get the dual solution, ie. the decomposition. 587 586 588 587 /// @{ … … 646 645 /// solution can be get with \c nodeValue(), \c blossomNum() and \c 647 646 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt 648 /// "BlossomIt" nested class which is able to iterate on the nodes647 /// "BlossomIt" nested class, which is able to iterate on the nodes 649 648 /// of a blossom. If the value type is integral then the dual 650 649 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". … … 1631 1630 1632 1631 /// \name Execution control 1633 /// The simplest way to execute the algorithm is to use the member1632 /// The simplest way to execute the algorithm is to use the 1634 1633 /// \c run() member function. 1635 1634 … … 1792 1791 1793 1792 /// \name Primal solution 1794 /// Functions forget 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.1799 /// 1800 /// Returns the matching value.1797 /// \brief Returns the weight of the matching. 1798 /// 1799 /// Returns the weight of the matching. 1801 1800 Value matchingValue() const { 1802 1801 Value sum = 0; … … 1849 1848 1850 1849 /// \name Dual solution 1851 /// Functions forget the dual solution.1850 /// Functions to get the dual solution. 1852 1851 1853 1852 /// @{ … … 1899 1898 } 1900 1899 1901 /// \brief Lemon iterator for get the items of the blossom.1902 /// 1903 /// Lemon iterator for getthe nodes of the blossom. This class1904 /// provides a common style lemon iterator which gives backa1900 /// \brief Iterator for obtaining the nodes of the blossom. 1901 /// 1902 /// Iterator for obtaining the nodes of the blossom. This class 1903 /// provides a common lemon style iterator for listing a 1905 1904 /// subset of the nodes. 1906 1905 class BlossomIt { … … 1909 1908 /// \brief Constructor. 1910 1909 /// 1911 /// Constructor forget the nodes of the variable.1910 /// Constructor to get the nodes of the variable. 1912 1911 BlossomIt(const MaxWeightedMatching& algorithm, int variable) 1913 1912 : _algorithm(&algorithm) … … 2818 2817 2819 2818 /// \name Execution control 2820 /// The simplest way to execute the algorithm is to use the member2819 /// The simplest way to execute the algorithm is to use the 2821 2820 /// \c run() member function. 2822 2821 … … 2956 2955 2957 2956 /// \name Primal solution 2958 /// Functions forget the primal solution, ie. the matching.2957 /// Functions to get the primal solution, ie. the matching. 2959 2958 2960 2959 /// @{ … … 2997 2996 2998 2997 /// \name Dual solution 2999 /// Functions forget the dual solution.2998 /// Functions to get the dual solution. 3000 2999 3001 3000 /// @{ … … 3047 3046 } 3048 3047 3049 /// \brief Lemon iterator for get the items of the blossom.3050 /// 3051 /// Lemon iterator for getthe nodes of the blossom. This class3052 /// provides a common style lemon iterator which gives backa3048 /// \brief Iterator for obtaining the nodes of the blossom. 3049 /// 3050 /// Iterator for obtaining the nodes of the blossom. This class 3051 /// provides a common lemon style iterator for listing a 3053 3052 /// subset of the nodes. 3054 3053 class BlossomIt { … … 3057 3056 /// \brief Constructor. 3058 3057 /// 3059 /// Constructor forget the nodes of the variable.3058 /// Constructor to get the nodes of the variable. 3060 3059 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable) 3061 3060 : _algorithm(&algorithm)
Note: See TracChangeset
for help on using the changeset viewer.
