Changeset 1587:8f1c317ebeb4 in lemon-0.x for lemon/max_matching.h
- Timestamp:
- 07/26/05 15:15:13 (19 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2091
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/max_matching.h
r1435 r1587 98 98 ///2*number of nodes), and a heuristical Edmonds' algorithm with a 99 99 ///heuristic of postponing shrinks for dense graphs. 100 inline void run(); 100 void run() { 101 if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) { 102 greedyMatching(); 103 runEdmonds(0); 104 } else runEdmonds(1); 105 } 106 101 107 102 108 ///Runs Edmonds' algorithm. … … 105 111 ///Edmonds' algorithm with a heuristic of postponing shrinks, 106 112 ///giving a faster algorithm for dense graphs. 107 void runEdmonds( int heur ); 113 void runEdmonds( int heur = 1 ) { 114 115 for(NodeIt v(g); v!=INVALID; ++v) 116 position.set(v,C); 117 118 typename Graph::template NodeMap<Node> ear(g,INVALID); 119 //undefined for the base nodes of the blossoms (i.e. for the 120 //representative elements of UFE blossom) and for the nodes in C 121 122 typename UFE::MapType blossom_base(g); 123 UFE blossom(blossom_base); 124 typename UFE::MapType tree_base(g); 125 UFE tree(tree_base); 126 //If these UFE's would be members of the class then also 127 //blossom_base and tree_base should be a member. 128 129 for(NodeIt v(g); v!=INVALID; ++v) { 130 if ( position[v]==C && _mate[v]==INVALID ) { 131 blossom.insert(v); 132 tree.insert(v); 133 position.set(v,D); 134 if ( heur == 1 ) lateShrink( v, ear, blossom, tree ); 135 else normShrink( v, ear, blossom, tree ); 136 } 137 } 138 } 139 108 140 109 141 ///Finds a greedy matching starting from the actual matching. … … 111 143 ///Starting form the actual matching stored, it finds a maximal 112 144 ///greedy matching. 113 void greedyMatching(); 145 void greedyMatching() { 146 for(NodeIt v(g); v!=INVALID; ++v) 147 if ( _mate[v]==INVALID ) { 148 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) { 149 Node y=g.runningNode(e); 150 if ( _mate[y]==INVALID && y!=v ) { 151 _mate.set(v,y); 152 _mate.set(y,v); 153 break; 154 } 155 } 156 } 157 } 114 158 115 159 ///Returns the size of the actual matching stored. … … 117 161 ///Returns the size of the actual matching stored. After \ref 118 162 ///run() it returns the size of a maximum matching in the graph. 119 int size() const; 163 int size() const { 164 int s=0; 165 for(NodeIt v(g); v!=INVALID; ++v) { 166 if ( _mate[v]!=INVALID ) { 167 ++s; 168 } 169 } 170 return s/2; 171 } 172 120 173 121 174 ///Resets the actual matching to the empty matching. … … 123 176 ///Resets the actual matching to the empty matching. 124 177 /// 125 void resetMatching(); 178 void resetMatching() { 179 for(NodeIt v(g); v!=INVALID; ++v) 180 _mate.set(v,INVALID); 181 } 126 182 127 183 ///Returns the mate of a node in the actual matching. … … 285 341 286 342 template <typename Graph> 287 void MaxMatching<Graph>::run() {288 if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {289 greedyMatching();290 runEdmonds(0);291 } else runEdmonds(1);292 }293 294 295 template <typename Graph>296 void MaxMatching<Graph>::runEdmonds( int heur=1 ) {297 298 for(NodeIt v(g); v!=INVALID; ++v)299 position.set(v,C);300 301 typename Graph::template NodeMap<Node> ear(g,INVALID);302 //undefined for the base nodes of the blossoms (i.e. for the303 //representative elements of UFE blossom) and for the nodes in C304 305 typename UFE::MapType blossom_base(g);306 UFE blossom(blossom_base);307 typename UFE::MapType tree_base(g);308 UFE tree(tree_base);309 //If these UFE's would be members of the class then also310 //blossom_base and tree_base should be a member.311 312 for(NodeIt v(g); v!=INVALID; ++v) {313 if ( position[v]==C && _mate[v]==INVALID ) {314 blossom.insert(v);315 tree.insert(v);316 position.set(v,D);317 if ( heur == 1 ) lateShrink( v, ear, blossom, tree );318 else normShrink( v, ear, blossom, tree );319 }320 }321 }322 323 324 template <typename Graph>325 343 void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, 326 344 UFE& blossom, UFE& tree) { … … 458 476 } 459 477 } 460 }461 462 template <typename Graph>463 void MaxMatching<Graph>::greedyMatching() {464 for(NodeIt v(g); v!=INVALID; ++v)465 if ( _mate[v]==INVALID ) {466 for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {467 Node y=g.runningNode(e);468 if ( _mate[y]==INVALID && y!=v ) {469 _mate.set(v,y);470 _mate.set(y,v);471 break;472 }473 }474 }475 }476 477 template <typename Graph>478 int MaxMatching<Graph>::size() const {479 int s=0;480 for(NodeIt v(g); v!=INVALID; ++v) {481 if ( _mate[v]!=INVALID ) {482 ++s;483 }484 }485 return s/2;486 }487 488 template <typename Graph>489 void MaxMatching<Graph>::resetMatching() {490 for(NodeIt v(g); v!=INVALID; ++v)491 _mate.set(v,INVALID);492 478 } 493 479
Note: See TracChangeset
for help on using the changeset viewer.