Index: lemon/max_matching.h
===================================================================
--- lemon/max_matching.h	(revision 1993)
+++ lemon/max_matching.h	(revision 2023)
@@ -115,4 +115,5 @@
     void runEdmonds( int heur = 1 ) {
       
+      //each vertex is put to C
       for(NodeIt v(g); v!=INVALID; ++v)
 	position.set(v,C);      
@@ -129,4 +130,9 @@
       //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,6 +230,6 @@
     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,6 +330,6 @@
 		    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,4 +337,8 @@
 		    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,6 +353,9 @@
 
   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,6 +367,11 @@
       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,40 +383,18 @@
 	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,4 +408,7 @@
 				      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,91 +423,59 @@
 	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,4 +485,6 @@
 				      UFE& blossom, UFE& tree,
 				      std::queue<Node>& Q) {
+    //We traverse a blossom and update everything.
+    
     ear.set(top,bottom);
     Node t=top;
@@ -538,4 +507,34 @@
   }
 
+
+  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,4 +550,5 @@
       _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,5 +561,5 @@
       } else position.set( it ,C);
     }
-    tree.eraseClass(x);
+    tree.eraseClass(y);
 
   }
