Changeset 640:7ac52d6a268e in lemon for lemon/max_matching.h
 Timestamp:
 04/17/09 09:54:14 (15 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/max_matching.h
r637 r640 41 41 /// 42 42 /// This class implements Edmonds' alternating forest matching algorithm 43 /// for finding a maximum cardinality matching in a general graph.43 /// for finding a maximum cardinality matching in a general undirected graph. 44 44 /// It can be started from an arbitrary initial matching 45 45 /// (the default is the empty one). … … 54 54 /// minus the number of barrier nodes is a lower bound on the 55 55 /// unmatched nodes, and the matching is optimal if and only if this bound is 56 /// tight. This decomposition can be obtained by calling \c57 /// decomposition() after running the algorithm.56 /// tight. This decomposition can be obtained using \ref status() or 57 /// \ref statusMap() after running the algorithm. 58 58 /// 59 /// \tparam GR The graph type the algorithm runs on.59 /// \tparam GR The undirected graph type the algorithm runs on. 60 60 template <typename GR> 61 61 class MaxMatching { … … 64 64 /// The graph type of the algorithm 65 65 typedef GR Graph; 66 /// The type of the matching map 66 67 typedef typename Graph::template NodeMap<typename Graph::Arc> 67 68 MatchingMap; … … 85 86 }; 86 87 88 /// The type of the status map 87 89 typedef typename Graph::template NodeMap<Status> StatusMap; 88 90 … … 584 586 } 585 587 588 /// \brief Return a const reference to the matching map. 589 /// 590 /// This function returns a const reference to a node map that stores 591 /// the matching arc (or edge) incident to each node. 592 const MatchingMap& matchingMap() const { 593 return *_matching; 594 } 595 586 596 /// \brief Return the mate of the given node. 587 597 /// … … 606 616 /// This function returns the \ref Status "status" of the given node 607 617 /// in the EdmondsGallai decomposition. 608 Status decomposition(const Node& n) const {618 Status status(const Node& n) const { 609 619 return (*_status)[n]; 620 } 621 622 /// \brief Return a const reference to the status map, which stores 623 /// the EdmondsGallai decomposition. 624 /// 625 /// This function returns a const reference to a node map that stores the 626 /// \ref Status "status" of each node in the EdmondsGallai decomposition. 627 const StatusMap& statusMap() const { 628 return *_status; 610 629 } 611 630 … … 663 682 /// by \ref MaxWeightedMatching::dualScale "4". 664 683 /// 665 /// \tparam GR The graph type the algorithm runs on.684 /// \tparam GR The undirected graph type the algorithm runs on. 666 685 /// \tparam WM The type edge weight map. The default type is 667 686 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". … … 682 701 typedef typename WeightMap::Value Value; 683 702 703 /// The type of the matching map 684 704 typedef typename Graph::template NodeMap<typename Graph::Arc> 685 705 MatchingMap; … … 1830 1850 /// 1831 1851 /// \pre Either run() or start() must be called before using this function. 1832 Value matching Value() const {1852 Value matchingWeight() const { 1833 1853 Value sum = 0; 1834 1854 for (NodeIt n(_graph); n != INVALID; ++n) { … … 1874 1894 Arc matching(const Node& node) const { 1875 1895 return (*_matching)[node]; 1896 } 1897 1898 /// \brief Return a const reference to the matching map. 1899 /// 1900 /// This function returns a const reference to a node map that stores 1901 /// the matching arc (or edge) incident to each node. 1902 const MatchingMap& matchingMap() const { 1903 return *_matching; 1876 1904 } 1877 1905 … … 2051 2079 /// by \ref MaxWeightedMatching::dualScale "4". 2052 2080 /// 2053 /// \tparam GR The graph type the algorithm runs on.2081 /// \tparam GR The undirected graph type the algorithm runs on. 2054 2082 /// \tparam WM The type edge weight map. The default type is 2055 2083 /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<int>". … … 2077 2105 std::numeric_limits<Value>::is_integer ? 4 : 1; 2078 2106 2107 /// The type of the matching map 2079 2108 typedef typename Graph::template NodeMap<typename Graph::Arc> 2080 2109 MatchingMap; … … 3039 3068 /// 3040 3069 /// \pre Either run() or start() must be called before using this function. 3041 Value matching Value() const {3070 Value matchingWeight() const { 3042 3071 Value sum = 0; 3043 3072 for (NodeIt n(_graph); n != INVALID; ++n) { … … 3068 3097 Arc matching(const Node& node) const { 3069 3098 return (*_matching)[node]; 3099 } 3100 3101 /// \brief Return a const reference to the matching map. 3102 /// 3103 /// This function returns a const reference to a node map that stores 3104 /// the matching arc (or edge) incident to each node. 3105 const MatchingMap& matchingMap() const { 3106 return *_matching; 3070 3107 } 3071 3108
Note: See TracChangeset
for help on using the changeset viewer.