COIN-OR::LEMON - Graph Library

Changeset 2023:f34f044a043c in lemon-0.x


Ignore:
Timestamp:
03/30/06 17:02:11 (18 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2661
Message:

Unionfind changes induced some bugs here. Also some augmentations made.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/max_matching.h

    r1993 r2023  
    115115    void runEdmonds( int heur = 1 ) {
    116116     
     117      //each vertex is put to C
    117118      for(NodeIt v(g); v!=INVALID; ++v)
    118119        position.set(v,C);     
     
    129130      //blossom_base and tree_base should be a member.
    130131     
     132      //We build only one tree and the other vertices uncovered by the
     133      //matching belong to C. (They can be considered as singleton
     134      //trees.) If this tree can be augmented or no more
     135      //grow/augmentation/shrink is possible then we return to this
     136      //"for" cycle.
    131137      for(NodeIt v(g); v!=INVALID; ++v) {
    132138        if ( position[v]==C && _mate[v]==INVALID ) {
     
    224230    template<typename NMapE>
    225231    void readNMapEdge(NMapE& map) {
    226      for(NodeIt v(g); v!=INVALID; ++v) {
    227        UEdge e=map[v];
     232      for(NodeIt v(g); v!=INVALID; ++v) {
     233        UEdge e=map[v];
    228234        if ( e!=INVALID )
    229235          _mate.set(v,g.oppositeNode(v,e));
     
    324330                    UFE& blossom, UFE& tree);
    325331
    326     bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear, 
    327                       UFE& blossom, UFE& tree, std::queue<Node>& Q);
     332    void shrink(Node x,Node y, typename Graph::template NodeMap<Node>& ear, 
     333                UFE& blossom, UFE& tree,std::queue<Node>& Q);
    328334
    329335    void shrinkStep(Node& top, Node& middle, Node& bottom,
     
    331337                    UFE& blossom, UFE& tree, std::queue<Node>& Q);
    332338
     339    bool growOrAugment(Node& y, Node& x, typename Graph::template
     340                       NodeMap<Node>& ear, UFE& blossom, UFE& tree,
     341                       std::queue<Node>& Q);
     342
    333343    void augment(Node x, typename Graph::template NodeMap<Node>& ear, 
    334344                 UFE& blossom, UFE& tree);
     
    343353
    344354  template <typename Graph>
    345   void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, 
    346                                       UFE& blossom, UFE& tree) {
     355  void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template
     356                                      NodeMap<Node>& ear, UFE& blossom, UFE& tree) {
     357    //We have one tree which we grow, and also shrink but only if it cannot be
     358    //postponed. If we augment then we return to the "for" cycle of
     359    //runEdmonds().
    347360
    348361    std::queue<Node> Q;   //queue of the totally unscanned nodes
     
    354367      Node x=Q.front();
    355368      Q.pop();
    356       if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
    357       else R.push(x);
     369      for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
     370        Node y=g.runningNode(e);
     371        //growOrAugment grows if y is covered by the matching and
     372        //augments if not. In this latter case it returns 1.
     373        if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return;
     374      }
     375      R.push(x);
    358376    }
    359377     
     
    365383        Node y=g.runningNode(e);
    366384
    367         if ( position[y] == D && blossom.find(x) != blossom.find(y) ) {
    368           //x and y must be in the same tree
     385        if ( position[y] == D && blossom.find(x) != blossom.find(y) ) 
     386          //Recall that we have only one tree.
     387          shrink( x, y, ear, blossom, tree, Q);
    369388       
    370           typename Graph::template NodeMap<bool> path(g,false);
    371 
    372           Node b=blossom.find(x);
    373           path.set(b,true);
    374           b=_mate[b];
    375           while ( b!=INVALID ) {
    376             b=blossom.find(ear[b]);
    377             path.set(b,true);
    378             b=_mate[b];
    379           } //going till the root
    380        
    381           Node top=y;
    382           Node middle=blossom.find(top);
    383           Node bottom=x;
    384           while ( !path[middle] )
    385             shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
    386                  
    387           Node base=middle;
    388           top=x;
    389           middle=blossom.find(top);
    390           bottom=y;
    391           Node blossom_base=blossom.find(base);
    392           while ( middle!=blossom_base )
    393             shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
    394                  
    395           blossom.makeRep(base);
    396         } // if shrink is needed
    397 
    398389        while ( !Q.empty() ) {
    399390          Node x=Q.front();
    400391          Q.pop();
    401           if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
    402           else R.push(x);
     392          for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
     393            Node y=g.runningNode(e);
     394            //growOrAugment grows if y is covered by the matching and
     395            //augments if not. In this latter case it returns 1.
     396            if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return;
     397          }
     398          R.push(x);
    403399        }
    404400      } //for e
     
    412408                                      NodeMap<Node>& ear, 
    413409                                      UFE& blossom, UFE& tree) {
     410    //We have one tree, which we grow and shrink. If we augment then we
     411    //return to the "for" cycle of runEdmonds().
     412   
    414413    std::queue<Node> Q;   //queue of the unscanned nodes
    415414    Q.push(v); 
     
    424423        switch ( position[y] ) {
    425424        case D:          //x and y must be in the same tree
    426 
    427           if ( blossom.find(x) != blossom.find(y) ) { //shrink
    428             typename Graph::template NodeMap<bool> path(g,false);
    429              
    430             Node b=blossom.find(x);
    431             path.set(b,true);
    432             b=_mate[b];
    433             while ( b!=INVALID ) {
    434               b=blossom.find(ear[b]);
    435               path.set(b,true);
    436               b=_mate[b];
    437             } //going till the root
    438        
    439             Node top=y;
    440             Node middle=blossom.find(top);
    441             Node bottom=x;
    442             while ( !path[middle] )
    443               shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
    444                
    445             Node base=middle;
    446             top=x;
    447             middle=blossom.find(top);
    448             bottom=y;
    449             Node blossom_base=blossom.find(base);
    450             while ( middle!=blossom_base )
    451               shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
    452                
    453             blossom.makeRep(base);
    454           }
     425          if ( blossom.find(x) != blossom.find(y) )
     426            //x and y are in the same tree
     427            shrink( x, y, ear, blossom, tree, Q);
    455428          break;
    456429        case C:
    457           if ( _mate[y]!=INVALID ) {   //grow
    458 
    459             ear.set(y,x);
    460             Node w=_mate[y];
    461             blossom.insert(w);
    462             position.set(y,A);
    463             position.set(w,D);
    464             tree.insert(y);
    465             tree.insert(w);
    466             tree.join(y,blossom.find(x)); 
    467             tree.join(w,y); 
    468             Q.push(w);
    469           } else {                 //augment 
    470             augment(x, ear, blossom, tree);
    471             _mate.set(x,y);
    472             _mate.set(y,x);
    473             return;
    474           } //if
     430          //growOrAugment grows if y is covered by the matching and
     431          //augments if not. In this latter case it returns 1.
     432          if ( growOrAugment(y, x, ear, blossom, tree, Q) ) return;
    475433          break;
    476434        default: break;
    477         }
     435        }
    478436      }
    479437    }
    480438  }
    481 
    482   template <typename Graph>
    483   bool MaxMatching<Graph>::noShrinkStep(Node x,
    484                                         typename Graph::template
    485                                         NodeMap<Node>& ear, 
    486                                         UFE& blossom, UFE& tree,
    487                                         std::queue<Node>& Q) {
    488     for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
    489       Node y=g.runningNode(e);
    490        
    491       if ( position[y]==C ) {
    492         if ( _mate[y]!=INVALID ) {       //grow
    493           ear.set(y,x);
    494           Node w=_mate[y];
    495           blossom.insert(w);
    496           position.set(y,A);
    497           position.set(w,D);
    498           tree.insert(y);
    499           tree.insert(w);
    500           tree.join(y,blossom.find(x)); 
    501           tree.join(w,y); 
    502           Q.push(w);
    503         } else {                      //augment
    504           augment(x, ear, blossom, tree);
    505           _mate.set(x,y);
    506           _mate.set(y,x);
    507           return true;
    508         }
    509       }
    510     }
    511     return false;
     439 
     440
     441  template <typename Graph>
     442    void MaxMatching<Graph>::shrink(Node x,Node y, typename
     443                                    Graph::template NodeMap<Node>& ear, 
     444                                    UFE& blossom, UFE& tree, std::queue<Node>& Q) {
     445    //x and y are the two adjacent vertices in two blossoms.
     446   
     447    typename Graph::template NodeMap<bool> path(g,false);
     448   
     449    Node b=blossom.find(x);
     450    path.set(b,true);
     451    b=_mate[b];
     452    while ( b!=INVALID ) {
     453      b=blossom.find(ear[b]);
     454      path.set(b,true);
     455      b=_mate[b];
     456    } //we go until the root through bases of blossoms and odd vertices
     457   
     458    Node top=y;
     459    Node middle=blossom.find(top);
     460    Node bottom=x;
     461    while ( !path[middle] )
     462      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
     463    //Until we arrive to a node on the path, we update blossom, tree
     464    //and the positions of the odd nodes.
     465   
     466    Node base=middle;
     467    top=x;
     468    middle=blossom.find(top);
     469    bottom=y;
     470    Node blossom_base=blossom.find(base);
     471    while ( middle!=blossom_base )
     472      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
     473    //Until we arrive to a node on the path, we update blossom, tree
     474    //and the positions of the odd nodes.
     475   
     476    blossom.makeRep(base);
    512477  }
     478
     479
    513480
    514481  template <typename Graph>
     
    518485                                      UFE& blossom, UFE& tree,
    519486                                      std::queue<Node>& Q) {
     487    //We traverse a blossom and update everything.
     488   
    520489    ear.set(top,bottom);
    521490    Node t=top;
     
    538507  }
    539508
     509
     510  template <typename Graph>
     511  bool MaxMatching<Graph>::growOrAugment(Node& y, Node& x, typename Graph::template
     512                                         NodeMap<Node>& ear, UFE& blossom, UFE& tree,
     513                                         std::queue<Node>& Q) {
     514    //x is in a blossom in the tree, y is outside. If y is covered by
     515    //the matching we grow, otherwise we augment. In this case we
     516    //return 1.
     517   
     518    if ( _mate[y]!=INVALID ) {       //grow
     519      ear.set(y,x);
     520      Node w=_mate[y];
     521      blossom.insert(w);
     522      position.set(y,A);
     523      position.set(w,D);
     524      tree.insert(y);
     525      tree.insert(w);
     526      tree.join(y,blossom.find(x)); 
     527      tree.join(w,y); 
     528      Q.push(w);
     529    } else {                      //augment
     530      augment(x, ear, blossom, tree);
     531      _mate.set(x,y);
     532      _mate.set(y,x);
     533      return true;
     534    }
     535    return false;
     536  }
     537 
     538
    540539  template <typename Graph>
    541540  void MaxMatching<Graph>::augment(Node x,
     
    551550      _mate.set(u,tmp);
    552551    }
     552    Node y=blossom.find(x);
    553553    typename UFE::ItemIt it;
    554554    for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
     
    561561      } else position.set( it ,C);
    562562    }
    563     tree.eraseClass(x);
     563    tree.eraseClass(y);
    564564
    565565  }
Note: See TracChangeset for help on using the changeset viewer.