Changeset 2023:f34f044a043c in lemon-0.x

Timestamp:

03/30/06 17:02:11 (19 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:

• lemon/max_matching.h (modified) (14 diffs)

lemon/max_matching.h

@@ -115 +115 @@
     void runEdmonds( int heur = 1 ) {
       
+      //each vertex is put to C
       for(NodeIt v(g); v!=INVALID; ++v)
         position.set(v,C);      
@@ -129 +130 @@
       //blossom_base and tree_base should be a member.
       
+      //We build only one tree and the other vertices uncovered by the
+      //matching belong to C. (They can be considered as singleton
+      //trees.) If this tree can be augmented or no more
+      //grow/augmentation/shrink is possible then we return to this
+      //"for" cycle.
       for(NodeIt v(g); v!=INVALID; ++v) {
         if ( position[v]==C && _mate[v]==INVALID ) {
@@ -224 +230 @@
     template<typename NMapE>
     void readNMapEdge(NMapE& map) {
-     for(NodeIt v(g); v!=INVALID; ++v) {
-       UEdge e=map[v];
+      for(NodeIt v(g); v!=INVALID; ++v) {
+        UEdge e=map[v];
         if ( e!=INVALID )
           _mate.set(v,g.oppositeNode(v,e));
@@ -324 +330 @@
                     UFE& blossom, UFE& tree);
 
-    bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear,  
-                      UFE& blossom, UFE& tree, std::queue<Node>& Q);
+    void shrink(Node x,Node y, typename Graph::template NodeMap<Node>& ear,  
+                UFE& blossom, UFE& tree,std::queue<Node>& Q);
 
     void shrinkStep(Node& top, Node& middle, Node& bottom,
@@ -331 +337 @@
                     UFE& blossom, UFE& tree, std::queue<Node>& Q);
 
+    bool growOrAugment(Node& y, Node& x, typename Graph::template 
+                       NodeMap<Node>& ear, UFE& blossom, UFE& tree, 
+                       std::queue<Node>& Q);
+
     void augment(Node x, typename Graph::template NodeMap<Node>& ear,  
                  UFE& blossom, UFE& tree);
@@ -343 +353 @@
 
   template <typename Graph>
-  void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,  
-                                      UFE& blossom, UFE& tree) {
+  void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template 
+                                      NodeMap<Node>& ear, UFE& blossom, UFE& tree) {
+    //We have one tree which we grow, and also shrink but only if it cannot be
+    //postponed. If we augment then we return to the "for" cycle of
+    //runEdmonds().
 
     std::queue<Node> Q;   //queue of the totally unscanned nodes
@@ -354 +367 @@
       Node x=Q.front();
       Q.pop();
-      if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
-      else R.push(x);
+      for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
+        Node y=g.runningNode(e);
+        //growOrAugment grows if y is covered by the matching and
+        //augments if not. In this latter case it returns 1.
+        if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return;
+      }
+      R.push(x);
     }
       
@@ -365 +383 @@
         Node y=g.runningNode(e);
 
-        if ( position[y] == D && blossom.find(x) != blossom.find(y) ) { 
-          //x and y must be in the same tree
+        if ( position[y] == D && blossom.find(x) != blossom.find(y) )  
+          //Recall that we have only one tree.
+          shrink( x, y, ear, blossom, tree, Q); 
         
-          typename Graph::template NodeMap<bool> path(g,false);
-
-          Node b=blossom.find(x);
-          path.set(b,true);
-          b=_mate[b];
-          while ( b!=INVALID ) { 
-            b=blossom.find(ear[b]);
-            path.set(b,true);
-            b=_mate[b];
-          } //going till the root
-        
-          Node top=y;
-          Node middle=blossom.find(top);
-          Node bottom=x;
-          while ( !path[middle] )
-            shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
-                  
-          Node base=middle;
-          top=x;
-          middle=blossom.find(top);
-          bottom=y;
-          Node blossom_base=blossom.find(base);
-          while ( middle!=blossom_base )
-            shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
-                  
-          blossom.makeRep(base);
-        } // if shrink is needed
-
         while ( !Q.empty() ) {
           Node x=Q.front();
           Q.pop();
-          if ( noShrinkStep(x, ear, blossom, tree, Q) ) return;
-          else R.push(x);
+          for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
+            Node y=g.runningNode(e);
+            //growOrAugment grows if y is covered by the matching and
+            //augments if not. In this latter case it returns 1.
+            if ( position[y]==C && growOrAugment(y, x, ear, blossom, tree, Q) ) return;
+          }
+          R.push(x);
         }
       } //for e
@@ -412 +408 @@
                                       NodeMap<Node>& ear,  
                                       UFE& blossom, UFE& tree) {
+    //We have one tree, which we grow and shrink. If we augment then we
+    //return to the "for" cycle of runEdmonds().
+    
     std::queue<Node> Q;   //queue of the unscanned nodes
     Q.push(v);  
@@ -424 +423 @@
         switch ( position[y] ) {
         case D:          //x and y must be in the same tree
-
-          if ( blossom.find(x) != blossom.find(y) ) { //shrink
-            typename Graph::template NodeMap<bool> path(g,false);
-              
-            Node b=blossom.find(x);
-            path.set(b,true);
-            b=_mate[b];
-            while ( b!=INVALID ) { 
-              b=blossom.find(ear[b]);
-              path.set(b,true);
-              b=_mate[b];
-            } //going till the root
-        
-            Node top=y;
-            Node middle=blossom.find(top);
-            Node bottom=x;
-            while ( !path[middle] )
-              shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
-                
-            Node base=middle;
-            top=x;
-            middle=blossom.find(top);
-            bottom=y;
-            Node blossom_base=blossom.find(base);
-            while ( middle!=blossom_base )
-              shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
-                
-            blossom.makeRep(base);
-          }
+          if ( blossom.find(x) != blossom.find(y) )
+            //x and y are in the same tree
+            shrink( x, y, ear, blossom, tree, Q);
           break;
         case C:
-          if ( _mate[y]!=INVALID ) {   //grow
-
-            ear.set(y,x);
-            Node w=_mate[y];
-            blossom.insert(w);
-            position.set(y,A); 
-            position.set(w,D); 
-            tree.insert(y);
-            tree.insert(w);
-            tree.join(y,blossom.find(x));  
-            tree.join(w,y);  
-            Q.push(w);
-          } else {                 //augment  
-            augment(x, ear, blossom, tree);
-            _mate.set(x,y);
-            _mate.set(y,x);
-            return;
-          } //if 
+          //growOrAugment grows if y is covered by the matching and
+          //augments if not. In this latter case it returns 1.
+          if ( growOrAugment(y, x, ear, blossom, tree, Q) ) return;
           break;
         default: break;
-        }
+        }
       }
     }
   }
-
-  template <typename Graph>
-  bool MaxMatching<Graph>::noShrinkStep(Node x,
-                                        typename Graph::template 
-                                        NodeMap<Node>& ear,  
-                                        UFE& blossom, UFE& tree,
-                                        std::queue<Node>& Q) {
-    for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
-      Node y=g.runningNode(e);
-        
-      if ( position[y]==C ) {
-        if ( _mate[y]!=INVALID ) {       //grow
-          ear.set(y,x);
-          Node w=_mate[y];
-          blossom.insert(w);
-          position.set(y,A);
-          position.set(w,D);
-          tree.insert(y);
-          tree.insert(w);
-          tree.join(y,blossom.find(x));  
-          tree.join(w,y);  
-          Q.push(w);
-        } else {                      //augment 
-          augment(x, ear, blossom, tree);
-          _mate.set(x,y);
-          _mate.set(y,x);
-          return true;
-        }
-      }
-    }
-    return false;
+  
+
+  template <typename Graph>
+    void MaxMatching<Graph>::shrink(Node x,Node y, typename 
+                                    Graph::template NodeMap<Node>& ear,  
+                                    UFE& blossom, UFE& tree, std::queue<Node>& Q) {
+    //x and y are the two adjacent vertices in two blossoms.
+   
+    typename Graph::template NodeMap<bool> path(g,false);
+    
+    Node b=blossom.find(x);
+    path.set(b,true);
+    b=_mate[b];
+    while ( b!=INVALID ) { 
+      b=blossom.find(ear[b]);
+      path.set(b,true);
+      b=_mate[b];
+    } //we go until the root through bases of blossoms and odd vertices
+    
+    Node top=y;
+    Node middle=blossom.find(top);
+    Node bottom=x;
+    while ( !path[middle] )
+      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
+    //Until we arrive to a node on the path, we update blossom, tree
+    //and the positions of the odd nodes.
+    
+    Node base=middle;
+    top=x;
+    middle=blossom.find(top);
+    bottom=y;
+    Node blossom_base=blossom.find(base);
+    while ( middle!=blossom_base )
+      shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
+    //Until we arrive to a node on the path, we update blossom, tree
+    //and the positions of the odd nodes.
+    
+    blossom.makeRep(base);
   }
+
+
 
   template <typename Graph>
@@ -518 +485 @@
                                       UFE& blossom, UFE& tree,
                                       std::queue<Node>& Q) {
+    //We traverse a blossom and update everything.
+    
     ear.set(top,bottom);
     Node t=top;
@@ -538 +507 @@
   }
 
+
+  template <typename Graph>
+  bool MaxMatching<Graph>::growOrAugment(Node& y, Node& x, typename Graph::template
+                                         NodeMap<Node>& ear, UFE& blossom, UFE& tree,
+                                         std::queue<Node>& Q) {
+    //x is in a blossom in the tree, y is outside. If y is covered by
+    //the matching we grow, otherwise we augment. In this case we
+    //return 1.
+    
+    if ( _mate[y]!=INVALID ) {       //grow
+      ear.set(y,x);
+      Node w=_mate[y];
+      blossom.insert(w);
+      position.set(y,A);
+      position.set(w,D);
+      tree.insert(y);
+      tree.insert(w);
+      tree.join(y,blossom.find(x));  
+      tree.join(w,y);  
+      Q.push(w);
+    } else {                      //augment 
+      augment(x, ear, blossom, tree);
+      _mate.set(x,y);
+      _mate.set(y,x);
+      return true;
+    }
+    return false;
+  }
+  
+
   template <typename Graph>
   void MaxMatching<Graph>::augment(Node x,
@@ -551 +550 @@
       _mate.set(u,tmp);
     }
+    Node y=blossom.find(x);
     typename UFE::ItemIt it;
     for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {   
@@ -561 +561 @@
       } else position.set( it ,C);
     }
-    tree.eraseClass(x);
+    tree.eraseClass(y);
 
   }