Main Page | Modules | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

max_matching.h

Go to the documentation of this file.
00001 /* -*- C++ -*-
00002  * src/lemon/max_matching.h - Part of LEMON, a generic C++ optimization library
00003  *
00004  * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
00005  * (Egervary Combinatorial Optimization Research Group, EGRES).
00006  *
00007  * Permission to use, modify and distribute this software is granted
00008  * provided that this copyright notice appears in all copies. For
00009  * precise terms see the accompanying LICENSE file.
00010  *
00011  * This software is provided "AS IS" with no warranty of any kind,
00012  * express or implied, and with no claim as to its suitability for any
00013  * purpose.
00014  *
00015  */
00016 
00017 #ifndef LEMON_MAX_MATCHING_H
00018 #define LEMON_MAX_MATCHING_H
00019 
00020 #include <queue>
00021 #include <lemon/invalid.h>
00022 #include <lemon/unionfind.h>
00023 #include <lemon/graph_utils.h>
00024 
00028 
00029 namespace lemon {
00030 
00033 
00035 
00055   template <typename Graph>
00056   class MaxMatching {
00057     typedef typename Graph::Node Node;
00058     typedef typename Graph::Edge Edge;
00059     typedef typename Graph::UndirEdgeIt UndirEdgeIt;
00060     typedef typename Graph::NodeIt NodeIt;
00061     typedef typename Graph::IncEdgeIt IncEdgeIt;
00062 
00063     typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;
00064 
00065   public:
00066     
00068 
00074     enum pos_enum {
00075       D=0,
00076       A=1,
00077       C=2
00078     }; 
00079 
00080   private:
00081 
00082     static const int HEUR_density=2;
00083     const Graph& g;
00084     typename Graph::template NodeMap<Node> _mate;
00085     typename Graph::template NodeMap<pos_enum> position;
00086      
00087   public:
00088     
00089     MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {}
00090 
00092 
00096     inline void run();
00097 
00099     
00103     void runEdmonds( int heur );
00104 
00106     
00109     void greedyMatching();
00110 
00112 
00115     int size() const;
00116 
00118 
00121     void resetMatching();
00122 
00124 
00127     Node mate(Node& node) const {
00128       return _mate[node];
00129     } 
00130 
00132 
00136     template<typename NMapN>
00137     void readNMapNode(NMapN& map) {
00138       for(NodeIt v(g); v!=INVALID; ++v) {
00139         _mate.set(v,map[v]);   
00140       } 
00141     } 
00142     
00144 
00148     template<typename NMapN>
00149     void writeNMapNode (NMapN& map) const {
00150       for(NodeIt v(g); v!=INVALID; ++v) {
00151         map.set(v,_mate[v]);   
00152       } 
00153     } 
00154 
00156 
00161     template<typename NMapE>
00162     void readNMapEdge(NMapE& map) {
00163      for(NodeIt v(g); v!=INVALID; ++v) {
00164         Edge e=map[v];
00165         if ( g.valid(e) )
00166           g.source(e) == v ? _mate.set(v,g.target(e)) : _mate.set(v,g.source(e)); 
00167       } 
00168     } 
00169     
00171 
00176     template<typename NMapE>
00177     void writeNMapEdge (NMapE& map)  const {
00178       typename Graph::template NodeMap<bool> todo(g,true); 
00179       for(NodeIt v(g); v!=INVALID; ++v) {
00180         if ( todo[v] && _mate[v]!=INVALID ) {
00181           Node u=_mate[v];
00182           for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
00183             if ( g.runningNode(e) == u ) {
00184               map.set(u,e);
00185               map.set(v,e);
00186               todo.set(u,false);
00187               todo.set(v,false);
00188               break;
00189             }
00190           }
00191         }
00192       } 
00193     }
00194 
00195 
00197     
00202     template<typename EMapB>
00203     void readEMapBool(EMapB& map) {
00204       for(UndirEdgeIt e(g); e!=INVALID; ++e) {
00205         if ( map[e] ) {
00206           Node u=g.source(e);     
00207           Node v=g.target(e);
00208           _mate.set(u,v);
00209           _mate.set(v,u);
00210         } 
00211       } 
00212     }
00213 
00214 
00216 
00221     template<typename EMapB>
00222     void writeEMapBool (EMapB& map) const {
00223       for(UndirEdgeIt e(g); e!=INVALID; ++e) map.set(e,false);
00224 
00225       typename Graph::template NodeMap<bool> todo(g,true); 
00226       for(NodeIt v(g); v!=INVALID; ++v) {
00227         if ( todo[v] && _mate[v]!=INVALID ) {
00228           Node u=_mate[v];
00229           for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
00230             if ( g.runningNode(e) == u ) {
00231               map.set(e,true);
00232               todo.set(u,false);
00233               todo.set(v,false);
00234               break;
00235             }
00236           }
00237         }
00238       } 
00239     }
00240 
00241 
00244 
00248     template<typename NMapEnum>
00249     void writePos (NMapEnum& map) const {
00250       for(NodeIt v(g); v!=INVALID; ++v)  map.set(v,position[v]);
00251     }
00252 
00253   private: 
00254 
00255     void lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
00256                     UFE& blossom, UFE& tree);
00257 
00258     void normShrink(Node v, typename Graph::NodeMap<Node>& ear,  
00259                     UFE& blossom, UFE& tree);
00260 
00261     bool noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear,  
00262                       UFE& blossom, UFE& tree, std::queue<Node>& Q);
00263 
00264     void shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear,  
00265                     UFE& blossom, UFE& tree, std::queue<Node>& Q);
00266 
00267     void augment(Node x, typename Graph::NodeMap<Node>& ear,  
00268                  UFE& blossom, UFE& tree);
00269 
00270   };
00271 
00272 
00273   // **********************************************************************
00274   //  IMPLEMENTATIONS
00275   // **********************************************************************
00276 
00277 
00278   template <typename Graph>
00279   void MaxMatching<Graph>::run() {
00280     if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
00281       greedyMatching();
00282       runEdmonds(0);
00283     } else runEdmonds(1);
00284   }
00285 
00286 
00287   template <typename Graph>
00288   void MaxMatching<Graph>::runEdmonds( int heur=1 ) {
00289 
00290     for(NodeIt v(g); v!=INVALID; ++v)
00291       position.set(v,C);      
00292 
00293     typename Graph::template NodeMap<Node> ear(g,INVALID); 
00294     //undefined for the base nodes of the blossoms (i.e. for the
00295     //representative elements of UFE blossom) and for the nodes in C
00296  
00297     typename UFE::MapType blossom_base(g);
00298     UFE blossom(blossom_base);
00299     typename UFE::MapType tree_base(g);
00300     UFE tree(tree_base);
00301 
00302     for(NodeIt v(g); v!=INVALID; ++v) {
00303       if ( position[v]==C && _mate[v]==INVALID ) {
00304         blossom.insert(v);
00305         tree.insert(v); 
00306         position.set(v,D);
00307         if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
00308         else normShrink( v, ear, blossom, tree );
00309       }
00310     }
00311   }
00312 
00313     
00314   template <typename Graph>
00315   void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
00316                                       UFE& blossom, UFE& tree) {
00317 
00318     std::queue<Node> Q;   //queue of the totally unscanned nodes
00319     Q.push(v);  
00320     std::queue<Node> R;   
00321     //queue of the nodes which must be scanned for a possible shrink
00322       
00323     while ( !Q.empty() ) {
00324       Node x=Q.front();
00325       Q.pop();
00326       if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
00327       else R.push(x);
00328     }
00329       
00330     while ( !R.empty() ) {
00331       Node x=R.front();
00332       R.pop();
00333         
00334       for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
00335         Node y=g.runningNode(e);
00336 
00337         if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { 
00338           //x and y must be in the same tree
00339         
00340           typename Graph::template NodeMap<bool> path(g,false);
00341 
00342           Node b=blossom.find(x);
00343           path.set(b,true);
00344           b=_mate[b];
00345           while ( b!=INVALID ) { 
00346             b=blossom.find(ear[b]);
00347             path.set(b,true);
00348             b=_mate[b];
00349           } //going till the root
00350         
00351           Node top=y;
00352           Node middle=blossom.find(top);
00353           Node bottom=x;
00354           while ( !path[middle] )
00355             shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
00356                   
00357           Node base=middle;
00358           top=x;
00359           middle=blossom.find(top);
00360           bottom=y;
00361           Node blossom_base=blossom.find(base);
00362           while ( middle!=blossom_base )
00363             shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
00364                   
00365           blossom.makeRep(base);
00366         } // if shrink is needed
00367 
00368         while ( !Q.empty() ) {
00369           Node x=Q.front();
00370           Q.pop();
00371           if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
00372           else R.push(x);
00373         }
00374       } //for e
00375     } // while ( !R.empty() )
00376   }
00377 
00378 
00379   template <typename Graph>
00380   void MaxMatching<Graph>::normShrink(Node v, typename Graph::NodeMap<Node>& ear,  
00381                                       UFE& blossom, UFE& tree) {
00382 
00383     std::queue<Node> Q;   //queue of the unscanned nodes
00384     Q.push(v);  
00385     while ( !Q.empty() ) {
00386 
00387       Node x=Q.front();
00388       Q.pop();
00389         
00390       for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
00391         Node y=g.runningNode(e);
00392               
00393         switch ( position[y] ) {
00394         case D:          //x and y must be in the same tree
00395 
00396           if ( blossom.find(x) != blossom.find(y) ) { //shrink
00397             typename Graph::template NodeMap<bool> path(g,false);
00398               
00399             Node b=blossom.find(x);
00400             path.set(b,true);
00401             b=_mate[b];
00402             while ( b!=INVALID ) { 
00403               b=blossom.find(ear[b]);
00404               path.set(b,true);
00405               b=_mate[b];
00406             } //going till the root
00407         
00408             Node top=y;
00409             Node middle=blossom.find(top);
00410             Node bottom=x;
00411             while ( !path[middle] )
00412               shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
00413                 
00414             Node base=middle;
00415             top=x;
00416             middle=blossom.find(top);
00417             bottom=y;
00418             Node blossom_base=blossom.find(base);
00419             while ( middle!=blossom_base )
00420               shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
00421                 
00422             blossom.makeRep(base);
00423           }
00424           break;
00425         case C:
00426           if ( _mate[y]!=INVALID ) {   //grow
00427 
00428             ear.set(y,x);
00429             Node w=_mate[y];
00430             blossom.insert(w);
00431             position.set(y,A); 
00432             position.set(w,D); 
00433             tree.insert(y);
00434             tree.insert(w);
00435             tree.join(y,blossom.find(x));  
00436             tree.join(w,y);  
00437             Q.push(w);
00438           } else {                 //augment  
00439             augment(x, ear, blossom, tree);
00440             _mate.set(x,y);
00441             _mate.set(y,x);
00442             return;
00443           } //if 
00444           break;
00445         default: break;
00446         }
00447       }
00448     }
00449   }
00450 
00451   template <typename Graph>
00452   void MaxMatching<Graph>::greedyMatching() {
00453     for(NodeIt v(g); v!=INVALID; ++v)
00454       if ( _mate[v]==INVALID ) {
00455         for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
00456           Node y=g.runningNode(e);
00457           if ( _mate[y]==INVALID && y!=v ) {
00458             _mate.set(v,y);
00459             _mate.set(y,v);
00460             break;
00461           }
00462         }
00463       } 
00464   }
00465    
00466   template <typename Graph>
00467   int MaxMatching<Graph>::size() const {
00468     int s=0;
00469     for(NodeIt v(g); v!=INVALID; ++v) {
00470       if ( _mate[v]!=INVALID ) {
00471         ++s;
00472       }
00473     }
00474     return (int)s/2;
00475   }
00476 
00477   template <typename Graph>
00478   void MaxMatching<Graph>::resetMatching() {
00479     for(NodeIt v(g); v!=INVALID; ++v)
00480       _mate.set(v,INVALID);      
00481   }
00482 
00483   template <typename Graph>
00484   bool MaxMatching<Graph>::noShrinkStep(Node x, typename Graph::NodeMap<Node>& ear,  
00485                                         UFE& blossom, UFE& tree, std::queue<Node>& Q) {
00486     for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
00487       Node y=g.runningNode(e);
00488         
00489       if ( position[y]==C ) {
00490         if ( _mate[y]!=INVALID ) {       //grow
00491           ear.set(y,x);
00492           Node w=_mate[y];
00493           blossom.insert(w);
00494           position.set(y,A);
00495           position.set(w,D);
00496           tree.insert(y);
00497           tree.insert(w);
00498           tree.join(y,blossom.find(x));  
00499           tree.join(w,y);  
00500           Q.push(w);
00501         } else {                      //augment 
00502           augment(x, ear, blossom, tree);
00503           _mate.set(x,y);
00504           _mate.set(y,x);
00505           return true;
00506         }
00507       }
00508     }
00509     return false;
00510   }
00511 
00512   template <typename Graph>
00513   void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom, typename Graph::NodeMap<Node>& ear,  
00514                                       UFE& blossom, UFE& tree, std::queue<Node>& Q) {
00515     ear.set(top,bottom);
00516     Node t=top;
00517     while ( t!=middle ) {
00518       Node u=_mate[t];
00519       t=ear[u];
00520       ear.set(t,u);
00521     } 
00522     bottom=_mate[middle];
00523     position.set(bottom,D);
00524     Q.push(bottom);
00525     top=ear[bottom];            
00526     Node oldmiddle=middle;
00527     middle=blossom.find(top);
00528     tree.erase(bottom);
00529     tree.erase(oldmiddle);
00530     blossom.insert(bottom);
00531     blossom.join(bottom, oldmiddle);
00532     blossom.join(top, oldmiddle);
00533   }
00534 
00535   template <typename Graph>
00536   void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear,  
00537                                    UFE& blossom, UFE& tree) { 
00538     Node v=_mate[x];
00539     while ( v!=INVALID ) {
00540         
00541       Node u=ear[v];
00542       _mate.set(v,u);
00543       Node tmp=v;
00544       v=_mate[u];
00545       _mate.set(u,tmp);
00546     }
00547     typename UFE::ItemIt it;
00548     for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
00549       if ( position[it] == D ) {
00550         typename UFE::ItemIt b_it;
00551         for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {  
00552           position.set( b_it ,C);
00553         }
00554         blossom.eraseClass(it);
00555       } else position.set( it ,C);
00556     }
00557     tree.eraseClass(x);
00558 
00559   }
00560 
00562   
00563 } //END OF NAMESPACE LEMON
00564 
00565 #endif //EDMONDS_H

Generated on Sat Mar 19 10:58:40 2005 for LEMON by  doxygen 1.4.1