Changeset 637:b61354458b59 in lemon for lemon
 Timestamp:
 04/15/09 12:01:14 (11 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

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 GallaiEdmonds decomposition of the49 /// graph. The nodes in \c EVEN/D induce a graph with50 /// factorcritical 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 factorcritical 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 GallaiEdmonds 50 /// decomposition of the graph. The nodes in \c EVEN/D induce a subgraph 51 /// with factorcritical 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 factorcritical 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 GallaiEdmonds decomposition of the graph. 68 /// 69 ///Indicates the GallaiEdmonds decomposition of the graph. The 70 ///nodes with Status \c EVEN/D induce a graph with factorcritical 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 GallaiEdmonds decomposition. 70 /// 71 ///These constants are used for indicating the GallaiEdmonds 72 ///decomposition of a graph. The nodes with status \c EVEN (or \c D) 73 ///induce a subgraph with factorcritical 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 GallaiEdmonds 599 /// decomposition. 586 600 587 601 /// @{ 588 602 589 /// \brief Return s the class of thenode in the EdmondsGallai603 /// \brief Return the status of the given node in the EdmondsGallai 590 604 /// decomposition. 591 605 /// 592 /// Returns the class of the node in the EdmondsGallai593 /// decomposition.606 /// This function returns the \ref Status "status" of the given node 607 /// in the EdmondsGallai 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
Note: See TracChangeset
for help on using the changeset viewer.