Changeset 637:b61354458b59 in lemon
- Timestamp:
- 04/15/09 12:01:14 (16 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 3 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/groups.dox
r633 r637 436 436 \brief Algorithms for finding matchings in graphs and bipartite graphs. 437 437 438 This group contains algorithm objects and functions to calculate438 This group contains the algorithms for calculating 439 439 matchings in graphs and bipartite graphs. The general matching problem is 440 finding a subset of the arcs which does not shares common endpoints. 440 finding a subset of the edges for which each node has at most one incident 441 edge. 441 442 442 443 There are several different algorithms for calculate matchings in -
lemon/max_matching.h
r628 r637 38 38 /// \ingroup matching 39 39 /// 40 /// \brief Edmonds' alternating forest maximum matching algorithm.40 /// \brief Maximum cardinality matching in general graphs 41 41 /// 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) 42 /// This class implements Edmonds' alternating forest matching algorithm 43 /// for finding a maximum cardinality matching in a general graph. 44 /// It can be started from an arbitrary initial matching 45 /// (the default is the empty one). 45 46 /// 46 47 /// 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 \c48 /// MATCHED/C showing the Gallai-Edmonds decomposition of the49 /// graph. The nodes in \c EVEN/D induce a graph with50 /// factor-critical components, the nodes in \c ODD/A form the51 /// barrier, and the nodes in \c MATCHED/C induce a graph having a52 /// perfect matching. The number of the factor-critical components48 /// \ref MaxMatching::Status "Status", having values \c EVEN (or \c D), 49 /// \c ODD (or \c A) and \c MATCHED (or \c C) defining the Gallai-Edmonds 50 /// decomposition of the graph. The nodes in \c EVEN/D induce a subgraph 51 /// with factor-critical components, the nodes in \c ODD/A form the 52 /// canonical barrier, and the nodes in \c MATCHED/C induce a graph having 53 /// a perfect matching. The number of the factor-critical components 53 54 /// minus the number of barrier nodes is a lower bound on the 54 55 /// unmatched nodes, and the matching is optimal if and only if this bound is 55 /// tight. This decomposition can be attained by calling \c56 /// tight. This decomposition can be obtained by calling \c 56 57 /// decomposition() after running the algorithm. 57 58 /// 58 /// \ param GR The graph type the algorithm runs on.59 /// \tparam GR The graph type the algorithm runs on. 59 60 template <typename GR> 60 61 class MaxMatching { 61 62 public: 62 63 64 /// The graph type of the algorithm 63 65 typedef GR Graph; 64 66 typedef typename Graph::template NodeMap<typename Graph::Arc> 65 67 MatchingMap; 66 68 67 ///\brief Indicates the Gallai-Edmonds decomposition of the graph. 68 /// 69 ///Indicates the Gallai-Edmonds decomposition of the graph. The 70 ///nodes with Status \c EVEN/D induce a graph with factor-critical 71 ///components, the nodes in \c ODD/A form the canonical barrier, 72 ///and the nodes in \c MATCHED/C induce a graph having a perfect 73 ///matching. 69 ///\brief Status constants for Gallai-Edmonds decomposition. 70 /// 71 ///These constants are used for indicating the Gallai-Edmonds 72 ///decomposition of a graph. The nodes with status \c EVEN (or \c D) 73 ///induce a subgraph with factor-critical components, the nodes with 74 ///status \c ODD (or \c A) form the canonical barrier, and the nodes 75 ///with status \c MATCHED (or \c C) induce a subgraph having a 76 ///perfect matching. 74 77 enum Status { 75 EVEN = 1, D = 1, MATCHED = 0, C = 0, ODD = -1, A = -1, UNMATCHED = -2 78 EVEN = 1, ///< = 1. (\c D is an alias for \c EVEN.) 79 D = 1, 80 MATCHED = 0, ///< = 0. (\c C is an alias for \c MATCHED.) 81 C = 0, 82 ODD = -1, ///< = -1. (\c A is an alias for \c ODD.) 83 A = -1, 84 UNMATCHED = -2 ///< = -2. 76 85 }; 77 86 … … 339 348 } 340 349 341 342 343 350 void extendOnArc(const Arc& a) { 344 351 Node base = _graph.source(a); … … 409 416 } 410 417 411 /// \name Execution control418 /// \name Execution Control 412 419 /// The simplest way to execute the algorithm is to use the 413 /// \c run() member function. 414 /// \n 415 416 /// If you need better control on the execution, you must call 417 /// \ref init(), \ref greedyInit() or \ref matchingInit() 418 /// functions first, then you can start the algorithm with the \ref 419 /// startSparse() or startDense() functions. 420 /// \c run() member function.\n 421 /// If you need better control on the execution, you have to call 422 /// one of the functions \ref init(), \ref greedyInit() or 423 /// \ref matchingInit() first, then you can start the algorithm with 424 /// \ref startSparse() or \ref startDense(). 420 425 421 426 ///@{ 422 427 423 /// \brief Sets the actual matching to the empty matching. 424 /// 425 /// Sets the actual matching to the empty matching. 426 /// 428 /// \brief Set the initial matching to the empty matching. 429 /// 430 /// This function sets the initial matching to the empty matching. 427 431 void init() { 428 432 createStructures(); … … 433 437 } 434 438 435 /// \brief Finds an initial matching in a greedy way436 /// 437 /// Itfinds an initial matching in a greedy way.439 /// \brief Find an initial matching in a greedy way. 440 /// 441 /// This function finds an initial matching in a greedy way. 438 442 void greedyInit() { 439 443 createStructures(); … … 459 463 460 464 461 /// \brief Initialize the matching from a map containing.462 /// 463 /// Initialize the matching from a \c bool valued \c Edge map. This464 /// map must have the property that there are no two incident edges465 /// with true value, ie. itcontains a matching.465 /// \brief Initialize the matching from a map. 466 /// 467 /// This function initializes the matching from a \c bool valued edge 468 /// map. This map should have the property that there are no two incident 469 /// edges with \c true value, i.e. it really contains a matching. 466 470 /// \return \c true if the map contains a matching. 467 471 template <typename MatchingMap> … … 490 494 } 491 495 492 /// \brief Starts Edmonds' algorithm 493 /// 494 /// If runs the original Edmonds' algorithm. 496 /// \brief Start Edmonds' algorithm 497 /// 498 /// This function runs the original Edmonds' algorithm. 499 /// 500 /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be 501 /// called before using this function. 495 502 void startSparse() { 496 503 for(NodeIt n(_graph); n != INVALID; ++n) { … … 504 511 } 505 512 506 /// \brief Starts Edmonds' algorithm. 507 /// 508 /// It runs Edmonds' algorithm with a heuristic of postponing 513 /// \brief Start Edmonds' algorithm with a heuristic improvement 514 /// for dense graphs 515 /// 516 /// This function runs Edmonds' algorithm with a heuristic of postponing 509 517 /// shrinks, therefore resulting in a faster algorithm for dense graphs. 518 /// 519 /// \pre \ref Init(), \ref greedyInit() or \ref matchingInit() must be 520 /// called before using this function. 510 521 void startDense() { 511 522 for(NodeIt n(_graph); n != INVALID; ++n) { … … 520 531 521 532 522 /// \brief Run sEdmonds' algorithm523 /// 524 /// Runs Edmonds' algorithm for sparse graphs (<tt>m<2*n</tt>)525 /// or Edmonds' algorithm with a heuristic of526 /// postponing shrinks for dense graphs.533 /// \brief Run Edmonds' algorithm 534 /// 535 /// This function runs Edmonds' algorithm. An additional heuristic of 536 /// postponing shrinks is used for relatively dense graphs 537 /// (for which <tt>m>=2*n</tt> holds). 527 538 void run() { 528 539 if (countEdges(_graph) < 2 * countNodes(_graph)) { … … 537 548 /// @} 538 549 539 /// \name Primal solution540 /// Functions to get the primal solution, i e. thematching.550 /// \name Primal Solution 551 /// Functions to get the primal solution, i.e. the maximum matching. 541 552 542 553 /// @{ 543 554 544 /// \brief Returns the size of the currentmatching.545 /// 546 /// Returns the size of the current matching. After \ref547 /// run() it returns the size of the maximum matching in the graph.555 /// \brief Return the size (cardinality) of the matching. 556 /// 557 /// This function returns the size (cardinality) of the current matching. 558 /// After run() it returns the size of the maximum matching in the graph. 548 559 int matchingSize() const { 549 560 int size = 0; … … 556 567 } 557 568 558 /// \brief Returns true when the edge is in the matching. 559 /// 560 /// Returns true when the edge is in the matching. 569 /// \brief Return \c true if the given edge is in the matching. 570 /// 571 /// This function returns \c true if the given edge is in the current 572 /// matching. 561 573 bool matching(const Edge& edge) const { 562 574 return edge == (*_matching)[_graph.u(edge)]; 563 575 } 564 576 565 /// \brief Returns the matching edge incident to the given node. 566 /// 567 /// Returns the matching edge of a \c node in the actual matching or 568 /// INVALID if the \c node is not covered by the actual matching. 577 /// \brief Return the matching arc (or edge) incident to the given node. 578 /// 579 /// This function returns the matching arc (or edge) incident to the 580 /// given node in the current matching or \c INVALID if the node is 581 /// not covered by the matching. 569 582 Arc matching(const Node& n) const { 570 583 return (*_matching)[n]; 571 584 } 572 585 573 /// \brief Returns the mate of a node in the actual matching.574 /// 575 /// Returns the mate of a \c node in the actual matching or576 /// INVALID if the \c node is not covered by the actualmatching.586 /// \brief Return the mate of the given node. 587 /// 588 /// This function returns the mate of the given node in the current 589 /// matching or \c INVALID if the node is not covered by the matching. 577 590 Node mate(const Node& n) const { 578 591 return (*_matching)[n] != INVALID ? … … 582 595 /// @} 583 596 584 /// \name Dual solution 585 /// Functions to get the dual solution, ie. the decomposition. 597 /// \name Dual Solution 598 /// Functions to get the dual solution, i.e. the Gallai-Edmonds 599 /// decomposition. 586 600 587 601 /// @{ 588 602 589 /// \brief Return s the class of thenode in the Edmonds-Gallai603 /// \brief Return the status of the given node in the Edmonds-Gallai 590 604 /// decomposition. 591 605 /// 592 /// Returns the class of the node in the Edmonds-Gallai593 /// decomposition.606 /// This function returns the \ref Status "status" of the given node 607 /// in the Edmonds-Gallai decomposition. 594 608 Status decomposition(const Node& n) const { 595 609 return (*_status)[n]; 596 610 } 597 611 598 /// \brief Return s true when thenode is in the barrier.599 /// 600 /// Returns true when thenode is in the barrier.612 /// \brief Return \c true if the given node is in the barrier. 613 /// 614 /// This function returns \c true if the given node is in the barrier. 601 615 bool barrier(const Node& n) const { 602 616 return (*_status)[n] == ODD; … … 616 630 /// \f$O(nm\log n)\f$ time complexity. 617 631 /// 618 /// The maximum weighted matching problem is to find undirected619 /// edges in the graph with maximum overall weight and no two of620 /// them shares their ends. The problem can be formulated with the621 /// following linear program.632 /// The maximum weighted matching problem is to find a subset of the 633 /// edges in an undirected graph with maximum overall weight for which 634 /// each node has at most one incident edge. 635 /// It can be formulated with the following linear program. 622 636 /// \f[ \sum_{e \in \delta(u)}x_e \le 1 \quad \forall u\in V\f] 623 637 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} … … 633 647 /// optimality. The solution of the dual problem can be used to check 634 648 /// the result of the algorithm. The dual linear problem is the 649 /// following. 635 650 /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)} 636 651 z_B \ge w_{uv} \quad \forall uv\in E\f] */ … … 640 655 \frac{\vert B \vert - 1}{2}z_B\f] */ 641 656 /// 642 /// The algorithm can be executed with \c run() or the \c init() and 643 /// then the \c start() member functions. After it the matching can 644 /// be asked with \c matching() or mate() functions. The dual 645 /// solution can be get with \c nodeValue(), \c blossomNum() and \c 646 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt 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 649 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". 657 /// The algorithm can be executed with the run() function. 658 /// After it the matching (the primal solution) and the dual solution 659 /// can be obtained using the query functions and the 660 /// \ref MaxWeightedMatching::BlossomIt "BlossomIt" nested class, 661 /// which is able to iterate on the nodes of a blossom. 662 /// If the value type is integer, then the dual solution is multiplied 663 /// by \ref MaxWeightedMatching::dualScale "4". 664 /// 665 /// \tparam GR The graph type the algorithm runs on. 666 /// \tparam WM The type edge weight map. The default type is 667 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". 668 #ifdef DOXYGEN 669 template <typename GR, typename WM> 670 #else 650 671 template <typename GR, 651 672 typename WM = typename GR::template EdgeMap<int> > 673 #endif 652 674 class MaxWeightedMatching { 653 675 public: 654 676 655 /// \e677 /// The graph type of the algorithm 656 678 typedef GR Graph; 657 /// \e679 /// The type of the edge weight map 658 680 typedef WM WeightMap; 659 /// \e681 /// The value type of the edge weights 660 682 typedef typename WeightMap::Value Value; 661 683 684 typedef typename Graph::template NodeMap<typename Graph::Arc> 685 MatchingMap; 686 662 687 /// \brief Scaling factor for dual solution 663 688 /// 664 /// Scaling factor for dual solution , it is equal to 4 or 1689 /// Scaling factor for dual solution. It is equal to 4 or 1 665 690 /// according to the value type. 666 691 static const int dualScale = 667 692 std::numeric_limits<Value>::is_integer ? 4 : 1; 668 669 typedef typename Graph::template NodeMap<typename Graph::Arc>670 MatchingMap;671 693 672 694 private: … … 1632 1654 } 1633 1655 1634 /// \name Execution control1656 /// \name Execution Control 1635 1657 /// The simplest way to execute the algorithm is to use the 1636 /// \ crun() member function.1658 /// \ref run() member function. 1637 1659 1638 1660 ///@{ … … 1640 1662 /// \brief Initialize the algorithm 1641 1663 /// 1642 /// Initialize the algorithm1664 /// This function initializes the algorithm. 1643 1665 void init() { 1644 1666 createStructures(); … … 1692 1714 } 1693 1715 1694 /// \brief Starts the algorithm 1695 /// 1696 /// Starts the algorithm 1716 /// \brief Start the algorithm 1717 /// 1718 /// This function starts the algorithm. 1719 /// 1720 /// \pre \ref init() must be called before using this function. 1697 1721 void start() { 1698 1722 enum OpType { … … 1777 1801 } 1778 1802 1779 /// \brief Run s %MaxWeightedMatchingalgorithm.1780 /// 1781 /// This method runs the %MaxWeightedMatching algorithm.1803 /// \brief Run the algorithm. 1804 /// 1805 /// This method runs the \c %MaxWeightedMatching algorithm. 1782 1806 /// 1783 1807 /// \note mwm.run() is just a shortcut of the following code. … … 1793 1817 /// @} 1794 1818 1795 /// \name Primal solution 1796 /// Functions to get the primal solution, ie. the matching. 1819 /// \name Primal Solution 1820 /// Functions to get the primal solution, i.e. the maximum weighted 1821 /// matching.\n 1822 /// Either \ref run() or \ref start() function should be called before 1823 /// using them. 1797 1824 1798 1825 /// @{ 1799 1826 1800 /// \brief Returns the weight of the matching. 1801 /// 1802 /// Returns the weight of the matching. 1827 /// \brief Return the weight of the matching. 1828 /// 1829 /// This function returns the weight of the found matching. 1830 /// 1831 /// \pre Either run() or start() must be called before using this function. 1803 1832 Value matchingValue() const { 1804 1833 Value sum = 0; … … 1811 1840 } 1812 1841 1813 /// \brief Returns the cardinality of the matching. 1814 /// 1815 /// Returns the cardinality of the matching. 1842 /// \brief Return the size (cardinality) of the matching. 1843 /// 1844 /// This function returns the size (cardinality) of the found matching. 1845 /// 1846 /// \pre Either run() or start() must be called before using this function. 1816 1847 int matchingSize() const { 1817 1848 int num = 0; … … 1824 1855 } 1825 1856 1826 /// \brief Returns true when the edge is in the matching. 1827 /// 1828 /// Returns true when the edge is in the matching. 1857 /// \brief Return \c true if the given edge is in the matching. 1858 /// 1859 /// This function returns \c true if the given edge is in the found 1860 /// matching. 1861 /// 1862 /// \pre Either run() or start() must be called before using this function. 1829 1863 bool matching(const Edge& edge) const { 1830 1864 return edge == (*_matching)[_graph.u(edge)]; 1831 1865 } 1832 1866 1833 /// \brief Returns the incident matching arc. 1834 /// 1835 /// Returns the incident matching arc from given node. If the 1836 /// node is not matched then it gives back \c INVALID. 1867 /// \brief Return the matching arc (or edge) incident to the given node. 1868 /// 1869 /// This function returns the matching arc (or edge) incident to the 1870 /// given node in the found matching or \c INVALID if the node is 1871 /// not covered by the matching. 1872 /// 1873 /// \pre Either run() or start() must be called before using this function. 1837 1874 Arc matching(const Node& node) const { 1838 1875 return (*_matching)[node]; 1839 1876 } 1840 1877 1841 /// \brief Returns the mate of the node. 1842 /// 1843 /// Returns the adjancent node in a mathcing arc. If the node is 1844 /// not matched then it gives back \c INVALID. 1878 /// \brief Return the mate of the given node. 1879 /// 1880 /// This function returns the mate of the given node in the found 1881 /// matching or \c INVALID if the node is not covered by the matching. 1882 /// 1883 /// \pre Either run() or start() must be called before using this function. 1845 1884 Node mate(const Node& node) const { 1846 1885 return (*_matching)[node] != INVALID ? … … 1850 1889 /// @} 1851 1890 1852 /// \name Dual solution 1853 /// Functions to get the dual solution. 1891 /// \name Dual Solution 1892 /// Functions to get the dual solution.\n 1893 /// Either \ref run() or \ref start() function should be called before 1894 /// using them. 1854 1895 1855 1896 /// @{ 1856 1897 1857 /// \brief Returns the value of the dual solution. 1858 /// 1859 /// Returns the value of the dual solution. It should be equal to 1860 /// the primal value scaled by \ref dualScale "dual scale". 1898 /// \brief Return the value of the dual solution. 1899 /// 1900 /// This function returns the value of the dual solution. 1901 /// It should be equal to the primal value scaled by \ref dualScale 1902 /// "dual scale". 1903 /// 1904 /// \pre Either run() or start() must be called before using this function. 1861 1905 Value dualValue() const { 1862 1906 Value sum = 0; … … 1870 1914 } 1871 1915 1872 /// \brief Returns the value of the node. 1873 /// 1874 /// Returns the the value of the node. 1916 /// \brief Return the dual value (potential) of the given node. 1917 /// 1918 /// This function returns the dual value (potential) of the given node. 1919 /// 1920 /// \pre Either run() or start() must be called before using this function. 1875 1921 Value nodeValue(const Node& n) const { 1876 1922 return (*_node_potential)[n]; 1877 1923 } 1878 1924 1879 /// \brief Returns the number of the blossoms in the basis. 1880 /// 1881 /// Returns the number of the blossoms in the basis. 1925 /// \brief Return the number of the blossoms in the basis. 1926 /// 1927 /// This function returns the number of the blossoms in the basis. 1928 /// 1929 /// \pre Either run() or start() must be called before using this function. 1882 1930 /// \see BlossomIt 1883 1931 int blossomNum() const { … … 1885 1933 } 1886 1934 1887 1888 /// \brief Returns the number of the nodes in the blossom. 1889 /// 1890 /// Returns the number of the nodes in the blossom. 1935 /// \brief Return the number of the nodes in the given blossom. 1936 /// 1937 /// This function returns the number of the nodes in the given blossom. 1938 /// 1939 /// \pre Either run() or start() must be called before using this function. 1940 /// \see BlossomIt 1891 1941 int blossomSize(int k) const { 1892 1942 return _blossom_potential[k].end - _blossom_potential[k].begin; 1893 1943 } 1894 1944 1895 /// \brief Returns the value of the blossom. 1896 /// 1897 /// Returns the the value of the blossom. 1898 /// \see BlossomIt 1945 /// \brief Return the dual value (ptential) of the given blossom. 1946 /// 1947 /// This function returns the dual value (ptential) of the given blossom. 1948 /// 1949 /// \pre Either run() or start() must be called before using this function. 1899 1950 Value blossomValue(int k) const { 1900 1951 return _blossom_potential[k].value; 1901 1952 } 1902 1953 1903 /// \brief Iterator for obtaining the nodes of the blossom. 1904 /// 1905 /// Iterator for obtaining the nodes of the blossom. This class 1906 /// provides a common lemon style iterator for listing a 1907 /// subset of the nodes. 1954 /// \brief Iterator for obtaining the nodes of a blossom. 1955 /// 1956 /// This class provides an iterator for obtaining the nodes of the 1957 /// given blossom. It lists a subset of the nodes. 1958 /// Before using this iterator, you must allocate a 1959 /// MaxWeightedMatching class and execute it. 1908 1960 class BlossomIt { 1909 1961 public: … … 1911 1963 /// \brief Constructor. 1912 1964 /// 1913 /// Constructor to get the nodes of the variable. 1965 /// Constructor to get the nodes of the given variable. 1966 /// 1967 /// \pre Either \ref MaxWeightedMatching::run() "algorithm.run()" or 1968 /// \ref MaxWeightedMatching::start() "algorithm.start()" must be 1969 /// called before initializing this iterator. 1914 1970 BlossomIt(const MaxWeightedMatching& algorithm, int variable) 1915 1971 : _algorithm(&algorithm) … … 1919 1975 } 1920 1976 1921 /// \brief Conversion to node.1977 /// \brief Conversion to \c Node. 1922 1978 /// 1923 /// Conversion to node.1979 /// Conversion to \c Node. 1924 1980 operator Node() const { 1925 1981 return _algorithm->_blossom_node_list[_index]; … … 1963 2019 /// \f$O(nm\log n)\f$ time complexity. 1964 2020 /// 1965 /// The maximum weighted matching problem is to find undirected1966 /// edges in the graph with maximum overall weight and no two of1967 /// them shares their ends and covers all nodes. The problem can be1968 /// formulated with the following linear program.2021 /// The maximum weighted perfect matching problem is to find a subset of 2022 /// the edges in an undirected graph with maximum overall weight for which 2023 /// each node has exactly one incident edge. 2024 /// It can be formulated with the following linear program. 1969 2025 /// \f[ \sum_{e \in \delta(u)}x_e = 1 \quad \forall u\in V\f] 1970 2026 /** \f[ \sum_{e \in \gamma(B)}x_e \le \frac{\vert B \vert - 1}{2} … … 1980 2036 /// optimality. The solution of the dual problem can be used to check 1981 2037 /// the result of the algorithm. The dual linear problem is the 2038 /// following. 1982 2039 /** \f[ y_u + y_v + \sum_{B \in \mathcal{O}, uv \in \gamma(B)}z_B \ge 1983 2040 w_{uv} \quad \forall uv\in E\f] */ … … 1986 2043 \frac{\vert B \vert - 1}{2}z_B\f] */ 1987 2044 /// 1988 /// The algorithm can be executed with \c run() or the \c init() and 1989 /// then the \c start() member functions. After it the matching can 1990 /// be asked with \c matching() or mate() functions. The dual 1991 /// solution can be get with \c nodeValue(), \c blossomNum() and \c 1992 /// blossomValue() members and \ref MaxWeightedMatching::BlossomIt 1993 /// "BlossomIt" nested class which is able to iterate on the nodes 1994 /// of a blossom. If the value type is integral then the dual 1995 /// solution is multiplied by \ref MaxWeightedMatching::dualScale "4". 2045 /// The algorithm can be executed with the run() function. 2046 /// After it the matching (the primal solution) and the dual solution 2047 /// can be obtained using the query functions and the 2048 /// \ref MaxWeightedPerfectMatching::BlossomIt "BlossomIt" nested class, 2049 /// which is able to iterate on the nodes of a blossom. 2050 /// If the value type is integer, then the dual solution is multiplied 2051 /// by \ref MaxWeightedMatching::dualScale "4". 2052 /// 2053 /// \tparam GR The graph type the algorithm runs on. 2054 /// \tparam WM The type edge weight map. The default type is 2055 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". 2056 #ifdef DOXYGEN 2057 template <typename GR, typename WM> 2058 #else 1996 2059 template <typename GR, 1997 2060 typename WM = typename GR::template EdgeMap<int> > 2061 #endif 1998 2062 class MaxWeightedPerfectMatching { 1999 2063 public: 2000 2064 2065 /// The graph type of the algorithm 2001 2066 typedef GR Graph; 2067 /// The type of the edge weight map 2002 2068 typedef WM WeightMap; 2069 /// The value type of the edge weights 2003 2070 typedef typename WeightMap::Value Value; 2004 2071 … … 2819 2886 } 2820 2887 2821 /// \name Execution control2888 /// \name Execution Control 2822 2889 /// The simplest way to execute the algorithm is to use the 2823 /// \ crun() member function.2890 /// \ref run() member function. 2824 2891 2825 2892 ///@{ … … 2827 2894 /// \brief Initialize the algorithm 2828 2895 /// 2829 /// Initialize the algorithm2896 /// This function initializes the algorithm. 2830 2897 void init() { 2831 2898 createStructures(); … … 2875 2942 } 2876 2943 2877 /// \brief Starts the algorithm 2878 /// 2879 /// Starts the algorithm 2944 /// \brief Start the algorithm 2945 /// 2946 /// This function starts the algorithm. 2947 /// 2948 /// \pre \ref init() must be called before using this function. 2880 2949 bool start() { 2881 2950 enum OpType { … … 2941 3010 } 2942 3011 2943 /// \brief Run s %MaxWeightedPerfectMatchingalgorithm.2944 /// 2945 /// This method runs the %MaxWeightedPerfectMatching algorithm.2946 /// 2947 /// \note mw m.run() is just a shortcut of the following code.3012 /// \brief Run the algorithm. 3013 /// 3014 /// This method runs the \c %MaxWeightedPerfectMatching algorithm. 3015 /// 3016 /// \note mwpm.run() is just a shortcut of the following code. 2948 3017 /// \code 2949 /// mw m.init();2950 /// mw m.start();3018 /// mwpm.init(); 3019 /// mwpm.start(); 2951 3020 /// \endcode 2952 3021 bool run() { … … 2957 3026 /// @} 2958 3027 2959 /// \name Primal solution 2960 /// Functions to get the primal solution, ie. the matching. 3028 /// \name Primal Solution 3029 /// Functions to get the primal solution, i.e. the maximum weighted 3030 /// perfect matching.\n 3031 /// Either \ref run() or \ref start() function should be called before 3032 /// using them. 2961 3033 2962 3034 /// @{ 2963 3035 2964 /// \brief Returns the matching value. 2965 /// 2966 /// Returns the matching value. 3036 /// \brief Return the weight of the matching. 3037 /// 3038 /// This function returns the weight of the found matching. 3039 /// 3040 /// \pre Either run() or start() must be called before using this function. 2967 3041 Value matchingValue() const { 2968 3042 Value sum = 0; … … 2975 3049 } 2976 3050 2977 /// \brief Returns true when the edge is in the matching. 2978 /// 2979 /// Returns true when the edge is in the matching. 3051 /// \brief Return \c true if the given edge is in the matching. 3052 /// 3053 /// This function returns \c true if the given edge is in the found 3054 /// matching. 3055 /// 3056 /// \pre Either run() or start() must be called before using this function. 2980 3057 bool matching(const Edge& edge) const { 2981 3058 return static_cast<const Edge&>((*_matching)[_graph.u(edge)]) == edge; 2982 3059 } 2983 3060 2984 /// \brief Returns the incident matching edge. 2985 /// 2986 /// Returns the incident matching arc from given edge. 3061 /// \brief Return the matching arc (or edge) incident to the given node. 3062 /// 3063 /// This function returns the matching arc (or edge) incident to the 3064 /// given node in the found matching or \c INVALID if the node is 3065 /// not covered by the matching. 3066 /// 3067 /// \pre Either run() or start() must be called before using this function. 2987 3068 Arc matching(const Node& node) const { 2988 3069 return (*_matching)[node]; 2989 3070 } 2990 3071 2991 /// \brief Returns the mate of the node. 2992 /// 2993 /// Returns the adjancent node in a mathcing arc. 3072 /// \brief Return the mate of the given node. 3073 /// 3074 /// This function returns the mate of the given node in the found 3075 /// matching or \c INVALID if the node is not covered by the matching. 3076 /// 3077 /// \pre Either run() or start() must be called before using this function. 2994 3078 Node mate(const Node& node) const { 2995 3079 return _graph.target((*_matching)[node]); … … 2998 3082 /// @} 2999 3083 3000 /// \name Dual solution 3001 /// Functions to get the dual solution. 3084 /// \name Dual Solution 3085 /// Functions to get the dual solution.\n 3086 /// Either \ref run() or \ref start() function should be called before 3087 /// using them. 3002 3088 3003 3089 /// @{ 3004 3090 3005 /// \brief Returns the value of the dual solution. 3006 /// 3007 /// Returns the value of the dual solution. It should be equal to 3008 /// the primal value scaled by \ref dualScale "dual scale". 3091 /// \brief Return the value of the dual solution. 3092 /// 3093 /// This function returns the value of the dual solution. 3094 /// It should be equal to the primal value scaled by \ref dualScale 3095 /// "dual scale". 3096 /// 3097 /// \pre Either run() or start() must be called before using this function. 3009 3098 Value dualValue() const { 3010 3099 Value sum = 0; … … 3018 3107 } 3019 3108 3020 /// \brief Returns the value of the node. 3021 /// 3022 /// Returns the the value of the node. 3109 /// \brief Return the dual value (potential) of the given node. 3110 /// 3111 /// This function returns the dual value (potential) of the given node. 3112 /// 3113 /// \pre Either run() or start() must be called before using this function. 3023 3114 Value nodeValue(const Node& n) const { 3024 3115 return (*_node_potential)[n]; 3025 3116 } 3026 3117 3027 /// \brief Returns the number of the blossoms in the basis. 3028 /// 3029 /// Returns the number of the blossoms in the basis. 3118 /// \brief Return the number of the blossoms in the basis. 3119 /// 3120 /// This function returns the number of the blossoms in the basis. 3121 /// 3122 /// \pre Either run() or start() must be called before using this function. 3030 3123 /// \see BlossomIt 3031 3124 int blossomNum() const { … … 3033 3126 } 3034 3127 3035 3036 /// \brief Returns the number of the nodes in the blossom. 3037 /// 3038 /// Returns the number of the nodes in the blossom. 3128 /// \brief Return the number of the nodes in the given blossom. 3129 /// 3130 /// This function returns the number of the nodes in the given blossom. 3131 /// 3132 /// \pre Either run() or start() must be called before using this function. 3133 /// \see BlossomIt 3039 3134 int blossomSize(int k) const { 3040 3135 return _blossom_potential[k].end - _blossom_potential[k].begin; 3041 3136 } 3042 3137 3043 /// \brief Returns the value of the blossom. 3044 /// 3045 /// Returns the the value of the blossom. 3046 /// \see BlossomIt 3138 /// \brief Return the dual value (ptential) of the given blossom. 3139 /// 3140 /// This function returns the dual value (ptential) of the given blossom. 3141 /// 3142 /// \pre Either run() or start() must be called before using this function. 3047 3143 Value blossomValue(int k) const { 3048 3144 return _blossom_potential[k].value; 3049 3145 } 3050 3146 3051 /// \brief Iterator for obtaining the nodes of the blossom. 3052 /// 3053 /// Iterator for obtaining the nodes of the blossom. This class 3054 /// provides a common lemon style iterator for listing a 3055 /// subset of the nodes. 3147 /// \brief Iterator for obtaining the nodes of a blossom. 3148 /// 3149 /// This class provides an iterator for obtaining the nodes of the 3150 /// given blossom. It lists a subset of the nodes. 3151 /// Before using this iterator, you must allocate a 3152 /// MaxWeightedPerfectMatching class and execute it. 3056 3153 class BlossomIt { 3057 3154 public: … … 3059 3156 /// \brief Constructor. 3060 3157 /// 3061 /// Constructor to get the nodes of the variable. 3158 /// Constructor to get the nodes of the given variable. 3159 /// 3160 /// \pre Either \ref MaxWeightedPerfectMatching::run() "algorithm.run()" 3161 /// or \ref MaxWeightedPerfectMatching::start() "algorithm.start()" 3162 /// must be called before initializing this iterator. 3062 3163 BlossomIt(const MaxWeightedPerfectMatching& algorithm, int variable) 3063 3164 : _algorithm(&algorithm) … … 3067 3168 } 3068 3169 3069 /// \brief Conversion to node.3170 /// \brief Conversion to \c Node. 3070 3171 /// 3071 /// Conversion to node.3172 /// Conversion to \c Node. 3072 3173 operator Node() const { 3073 3174 return _algorithm->_blossom_node_list[_index]; … … 3084 3185 /// \brief Validity checking 3085 3186 /// 3086 /// Checks whether the iterator is invalid.3187 /// This function checks whether the iterator is invalid. 3087 3188 bool operator==(Invalid) const { return _index == _last; } 3088 3189 3089 3190 /// \brief Validity checking 3090 3191 /// 3091 /// Checks whether the iterator is valid.3192 /// This function checks whether the iterator is valid. 3092 3193 bool operator!=(Invalid) const { return _index != _last; } 3093 3194 … … 3102 3203 }; 3103 3204 3104 3105 3205 } //END OF NAMESPACE LEMON 3106 3206 -
test/max_matching_test.cc
r463 r637 21 21 #include <vector> 22 22 #include <queue> 23 #include <lemon/math.h>24 23 #include <cstdlib> 25 24 26 25 #include <lemon/max_matching.h> 27 26 #include <lemon/smart_graph.h> 27 #include <lemon/concepts/graph.h> 28 #include <lemon/concepts/maps.h> 28 29 #include <lemon/lgf_reader.h> 30 #include <lemon/math.h> 29 31 30 32 #include "test_tools.h" … … 111 113 }; 112 114 115 void checkMaxMatchingCompile() 116 { 117 typedef concepts::Graph Graph; 118 typedef Graph::Node Node; 119 typedef Graph::Edge Edge; 120 typedef Graph::EdgeMap<bool> MatMap; 121 122 Graph g; 123 Node n; 124 Edge e; 125 MatMap mat(g); 126 127 MaxMatching<Graph> mat_test(g); 128 const MaxMatching<Graph>& 129 const_mat_test = mat_test; 130 131 mat_test.init(); 132 mat_test.greedyInit(); 133 mat_test.matchingInit(mat); 134 mat_test.startSparse(); 135 mat_test.startDense(); 136 mat_test.run(); 137 138 const_mat_test.matchingSize(); 139 const_mat_test.matching(e); 140 const_mat_test.matching(n); 141 const_mat_test.mate(n); 142 143 MaxMatching<Graph>::Status stat = 144 const_mat_test.decomposition(n); 145 const_mat_test.barrier(n); 146 147 ignore_unused_variable_warning(stat); 148 } 149 150 void checkMaxWeightedMatchingCompile() 151 { 152 typedef concepts::Graph Graph; 153 typedef Graph::Node Node; 154 typedef Graph::Edge Edge; 155 typedef Graph::EdgeMap<int> WeightMap; 156 157 Graph g; 158 Node n; 159 Edge e; 160 WeightMap w(g); 161 162 MaxWeightedMatching<Graph> mat_test(g, w); 163 const MaxWeightedMatching<Graph>& 164 const_mat_test = mat_test; 165 166 mat_test.init(); 167 mat_test.start(); 168 mat_test.run(); 169 170 const_mat_test.matchingValue(); 171 const_mat_test.matchingSize(); 172 const_mat_test.matching(e); 173 const_mat_test.matching(n); 174 const_mat_test.mate(n); 175 176 int k = 0; 177 const_mat_test.dualValue(); 178 const_mat_test.nodeValue(n); 179 const_mat_test.blossomNum(); 180 const_mat_test.blossomSize(k); 181 const_mat_test.blossomValue(k); 182 } 183 184 void checkMaxWeightedPerfectMatchingCompile() 185 { 186 typedef concepts::Graph Graph; 187 typedef Graph::Node Node; 188 typedef Graph::Edge Edge; 189 typedef Graph::EdgeMap<int> WeightMap; 190 191 Graph g; 192 Node n; 193 Edge e; 194 WeightMap w(g); 195 196 MaxWeightedPerfectMatching<Graph> mat_test(g, w); 197 const MaxWeightedPerfectMatching<Graph>& 198 const_mat_test = mat_test; 199 200 mat_test.init(); 201 mat_test.start(); 202 mat_test.run(); 203 204 const_mat_test.matchingValue(); 205 const_mat_test.matching(e); 206 const_mat_test.matching(n); 207 const_mat_test.mate(n); 208 209 int k = 0; 210 const_mat_test.dualValue(); 211 const_mat_test.nodeValue(n); 212 const_mat_test.blossomNum(); 213 const_mat_test.blossomSize(k); 214 const_mat_test.blossomValue(k); 215 } 216 113 217 void checkMatching(const SmartGraph& graph, 114 218 const MaxMatching<SmartGraph>& mm) {
Note: See TracChangeset
for help on using the changeset viewer.