Changeset 593:7ac52d6a268e in lemon1.2
 Timestamp:
 04/17/09 09:54:14 (10 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/max_matching.h
r590 r593 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 
test/max_matching_test.cc
r590 r593 139 139 const_mat_test.matching(e); 140 140 const_mat_test.matching(n); 141 const MaxMatching<Graph>::MatchingMap& mmap = 142 const_mat_test.matchingMap(); 143 e = mmap[n]; 141 144 const_mat_test.mate(n); 142 145 143 146 MaxMatching<Graph>::Status stat = 144 const_mat_test.decomposition(n); 147 const_mat_test.status(n); 148 const MaxMatching<Graph>::StatusMap& smap = 149 const_mat_test.statusMap(); 150 stat = smap[n]; 145 151 const_mat_test.barrier(n); 146 147 ignore_unused_variable_warning(stat);148 152 } 149 153 … … 168 172 mat_test.run(); 169 173 170 const_mat_test.matching Value();174 const_mat_test.matchingWeight(); 171 175 const_mat_test.matchingSize(); 172 176 const_mat_test.matching(e); 173 177 const_mat_test.matching(n); 178 const MaxWeightedMatching<Graph>::MatchingMap& mmap = 179 const_mat_test.matchingMap(); 180 e = mmap[n]; 174 181 const_mat_test.mate(n); 175 182 … … 202 209 mat_test.run(); 203 210 204 const_mat_test.matching Value();211 const_mat_test.matchingWeight(); 205 212 const_mat_test.matching(e); 206 213 const_mat_test.matching(n); 214 const MaxWeightedPerfectMatching<Graph>::MatchingMap& mmap = 215 const_mat_test.matchingMap(); 216 e = mmap[n]; 207 217 const_mat_test.mate(n); 208 218 … … 225 235 226 236 for (NodeIt n(graph); n != INVALID; ++n) { 227 check(mm. decomposition(n) == MaxMatching<SmartGraph>::EVEN 237 check(mm.status(n) == MaxMatching<SmartGraph>::EVEN  228 238 mm.matching(n) != INVALID, "Wrong GallaiEdmonds decomposition"); 229 if (mm. decomposition(n) == MaxMatching<SmartGraph>::ODD) {239 if (mm.status(n) == MaxMatching<SmartGraph>::ODD) { 230 240 ++barrier_num; 231 241 } else { … … 240 250 ++num; 241 251 } 242 check(mm. decomposition(graph.u(e)) != MaxMatching<SmartGraph>::EVEN 243 mm. decomposition(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED,252 check(mm.status(graph.u(e)) != MaxMatching<SmartGraph>::EVEN  253 mm.status(graph.v(e)) != MaxMatching<SmartGraph>::MATCHED, 244 254 "Wrong GallaiEdmonds decomposition"); 245 255 246 check(mm. decomposition(graph.v(e)) != MaxMatching<SmartGraph>::EVEN 247 mm. decomposition(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED,256 check(mm.status(graph.v(e)) != MaxMatching<SmartGraph>::EVEN  257 mm.status(graph.u(e)) != MaxMatching<SmartGraph>::MATCHED, 248 258 "Wrong GallaiEdmonds decomposition"); 249 259 250 if (mm. decomposition(graph.u(e)) != MaxMatching<SmartGraph>::ODD &&251 mm. decomposition(graph.v(e)) != MaxMatching<SmartGraph>::ODD) {260 if (mm.status(graph.u(e)) != MaxMatching<SmartGraph>::ODD && 261 mm.status(graph.v(e)) != MaxMatching<SmartGraph>::ODD) { 252 262 comp.join(graph.u(e), graph.v(e)); 253 263 } … … 257 267 int odd_comp_num = 0; 258 268 for (NodeIt n(graph); n != INVALID; ++n) { 259 if (mm. decomposition(n) != MaxMatching<SmartGraph>::ODD) {269 if (mm.status(n) != MaxMatching<SmartGraph>::ODD) { 260 270 int root = comp.find(n); 261 271 if (comp_root.find(root) == comp_root.end()) {
Note: See TracChangeset
for help on using the changeset viewer.