Changeset 1090:9e9195331ea6 in lemon-0.x
- Timestamp:
- 01/20/05 11:24:38 (20 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1486
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/lemon/max_matching.h
r1077 r1090 48 48 ///barrier, and the nodes in C induce a graph having a perfect 49 49 ///matching. This decomposition can be attained by calling \ref 50 ///writePos after running the algorithm. Before subsequent runs, 51 ///the function \ref resetPos() must be called. 50 ///writePos after running the algorithm. 52 51 /// 53 52 ///\param Graph The undirected graph type the algorithm runs on. … … 88 87 public: 89 88 90 MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g ,C) {}89 MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g) {} 91 90 92 91 ///Runs Edmonds' algorithm. … … 94 93 ///Runs Edmonds' algorithm for sparse graphs (number of edges < 95 94 ///2*number of nodes), and a heuristical Edmonds' algorithm with a 96 ///heuristic of postponing shrinks for dense graphs. \pre Before 97 ///the subsequent calls \ref resetPos must be called. 95 ///heuristic of postponing shrinks for dense graphs. 98 96 inline void run(); 99 97 … … 102 100 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs 103 101 ///Edmonds' algorithm with a heuristic of postponing shrinks, 104 ///giving a faster algorithm for dense graphs. \pre Before the 105 ///subsequent calls \ref resetPos must be called. 102 ///giving a faster algorithm for dense graphs. 106 103 void runEdmonds( int heur ); 107 104 … … 117 114 ///run() it returns the size of a maximum matching in the graph. 118 115 int size() const; 119 120 ///Resets the map storing the Gallai-Edmonds decomposition.121 122 ///Resets the map storing the Gallai-Edmonds decomposition of the123 ///graph, making it possible to run the algorithm. Must be called124 ///before all runs of the Edmonds algorithm, except for the first125 ///run.126 void resetPos();127 116 128 117 ///Resets the actual matching to the empty matching. … … 246 235 ///the algorithm. 247 236 248 ///After calling any run methods of the class, and before calling 249 ///\ref resetPos(), it writes the Gallai-Edmonds canonical 250 ///decomposition of the graph. \c map must be a node map 251 ///of \ref pos_enum 's. 237 ///After calling any run methods of the class, it writes the 238 ///Gallai-Edmonds canonical decomposition of the graph. \c map 239 ///must be a node map of \ref pos_enum 's. 252 240 template<typename NMapEnum> 253 241 void writePos (NMapEnum& map) const { … … 291 279 template <typename Graph> 292 280 void MaxMatching<Graph>::runEdmonds( int heur=1 ) { 293 281 282 for(NodeIt v(g); v!=INVALID; ++v) 283 position.set(v,C); 284 294 285 typename Graph::template NodeMap<Node> ear(g,INVALID); 295 286 //undefined for the base nodes of the blossoms (i.e. for the … … 474 465 } 475 466 return (int)s/2; 476 }477 478 template <typename Graph>479 void MaxMatching<Graph>::resetPos() {480 for(NodeIt v(g); v!=INVALID; ++v)481 position.set(v,C);482 467 } 483 468
Note: See TracChangeset
for help on using the changeset viewer.