lemon-0.x: comparison lemon/max

equal deleted inserted replaced

-:98c4d3006431
+:38ce1bdee72d
 ///If heur=0 it runs Edmonds' algorithm. If heur=1 it runs
 ///Edmonds' algorithm with a heuristic of postponing shrinks,
 ///giving a faster algorithm for dense graphs.
 void runEdmonds( int heur = 1 ) {
+//each vertex is put to C
 for(NodeIt v(g); v!=INVALID; ++v)
 	position.set(v,C);
 typename Graph::template NodeMap<Node> ear(g,INVALID);
 //undefined for the base nodes of the blossoms (i.e. for the
 typename UFE::MapType tree_base(g);
 UFE tree(tree_base);
 //If these UFE's would be members of the class then also
 //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 ) {
 	  blossom.insert(v);
 	  tree.insert(v);
 	  position.set(v,D);
 ///have the property that if \c g.oppositeNode(u,map[u])==v then
 ///\c \c g.oppositeNode(v,map[v])==u holds, and now some edge
 ///joining \c u to \c v will be an edge of the matching.
 template<typename NMapE>
 void readNMapEdge(NMapE& map) {
 for(NodeIt v(g); v!=INVALID; ++v) {
-UEdge e=map[v];
+	UEdge e=map[v];
 	if ( e!=INVALID )
 	  _mate.set(v,g.oppositeNode(v,e));
 }
 }
 		    UFE& blossom, UFE& tree);
 void normShrink(Node v, typename Graph::template NodeMap<Node>& ear,
 		    UFE& blossom, UFE& tree);
-bool noShrinkStep(Node x, typename Graph::template NodeMap<Node>& ear,
+void shrink(Node x,Node y, typename Graph::template NodeMap<Node>& ear,
-		      UFE& blossom, UFE& tree, std::queue<Node>& Q);
+		UFE& blossom, UFE& tree,std::queue<Node>& Q);
 void shrinkStep(Node& top, Node& middle, Node& bottom,
 		    typename Graph::template NodeMap<Node>& ear,
 		    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);
 };
 //  IMPLEMENTATIONS
 // **********************************************************************
 template <typename Graph>
-void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear,
+void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template
-				      UFE& blossom, UFE& tree) {
+				      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
 Q.push(v);
 std::queue<Node> R;
 //queue of the nodes which must be scanned for a possible shrink
 while ( !Q.empty() ) {
 Node x=Q.front();
 Q.pop();
-if ( noShrinkStep( x, ear, blossom, tree, Q ) ) return;
+for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
-else R.push(x);
+	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);
 }
 while ( !R.empty() ) {
 Node x=R.front();
 R.pop();
 for( IncEdgeIt e(g,x); e!=INVALID ; ++e ) {
 	Node y=g.runningNode(e);
-	if ( position[y] == D && blossom.find(x) != blossom.find(y) ) {
+	if ( position[y] == D && blossom.find(x) != blossom.find(y) )
-	  //x and y must be in the same tree
+	  //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;
+	  for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
-	  else R.push(x);
+	    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
 } // while ( !R.empty() )
 }
 template <typename Graph>
 void MaxMatching<Graph>::normShrink(Node v,
 				      typename Graph::template
 				      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);
 while ( !Q.empty() ) {
 Node x=Q.front();
 for( IncEdgeIt e(g,x); e!=INVALID; ++e ) {
 	Node y=g.runningNode(e);
 	switch ( position[y] ) {
 	case D:          //x and y must be in the same tree
+	  if ( blossom.find(x) != blossom.find(y) )
-	  if ( blossom.find(x) != blossom.find(y) ) { //shrink
+	    //x and y are in the same tree
-	    typename Graph::template NodeMap<bool> path(g,false);
+	    shrink( x, y, ear, blossom, tree, Q);
-	    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);
-	  }
 	  break;
 	case C:
-	  if ( _mate[y]!=INVALID ) {   //grow
+	  //growOrAugment grows if y is covered by the matching and
+	  //augments if not. In this latter case it returns 1.
-	    ear.set(y,x);
+	  if ( growOrAugment(y, x, ear, blossom, tree, Q) ) return;
-	    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
 	  break;
 	default: break;
 	}
 }
 }
 }
-template <typename Graph>
-bool MaxMatching<Graph>::noShrinkStep(Node x,
+template <typename Graph>
-					typename Graph::template
+void MaxMatching<Graph>::shrink(Node x,Node y, typename
-					NodeMap<Node>& ear,
+				    Graph::template NodeMap<Node>& ear,
-					UFE& blossom, UFE& tree,
+				    UFE& blossom, UFE& tree, std::queue<Node>& Q) {
-					std::queue<Node>& Q) {
+//x and y are the two adjacent vertices in two blossoms.
-for( IncEdgeIt e(g,x); e!= INVALID; ++e ) {
-Node y=g.runningNode(e);
+typename Graph::template NodeMap<bool> path(g,false);
-if ( position[y]==C ) {
+Node b=blossom.find(x);
-	if ( _mate[y]!=INVALID ) {       //grow
+path.set(b,true);
-	  ear.set(y,x);
+b=_mate[b];
-	  Node w=_mate[y];
+while ( b!=INVALID ) {
-	  blossom.insert(w);
+b=blossom.find(ear[b]);
-	  position.set(y,A);
+path.set(b,true);
-	  position.set(w,D);
+b=_mate[b];
-	  tree.insert(y);
+} //we go until the root through bases of blossoms and odd vertices
-	  tree.insert(w);
-	  tree.join(y,blossom.find(x));
+Node top=y;
-	  tree.join(w,y);
+Node middle=blossom.find(top);
-	  Q.push(w);
+Node bottom=x;
-	} else {                      //augment
+while ( !path[middle] )
-	  augment(x, ear, blossom, tree);
+shrinkStep(top, middle, bottom, ear, blossom, tree, Q);
-	  _mate.set(x,y);
+//Until we arrive to a node on the path, we update blossom, tree
-	  _mate.set(y,x);
+//and the positions of the odd nodes.
-	  return true;
-	}
+Node base=middle;
-}
+top=x;
-}
+middle=blossom.find(top);
-return false;
+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>
 void MaxMatching<Graph>::shrinkStep(Node& top, Node& middle, Node& bottom,
 				      typename Graph::template
 				      NodeMap<Node>& ear,
 				      UFE& blossom, UFE& tree,
 				      std::queue<Node>& Q) {
+//We traverse a blossom and update everything.
 ear.set(top,bottom);
 Node t=top;
 while ( t!=middle ) {
 Node u=_mate[t];
 t=ear[u];
 blossom.insert(bottom);
 blossom.join(bottom, oldmiddle);
 blossom.join(top, oldmiddle);
 }
+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,
 				   typename Graph::template NodeMap<Node>& ear,
 				   UFE& blossom, UFE& tree) {
 Node v=_mate[x];
 _mate.set(v,u);
 Node tmp=v;
 v=_mate[u];
 _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)) {
 if ( position[it] == D ) {
 	typename UFE::ItemIt b_it;
 	for (blossom.first(b_it,it); blossom.valid(b_it); blossom.next(b_it)) {
 	  position.set( b_it ,C);
 	}
 	blossom.eraseClass(it);
 } else position.set( it ,C);
 }
-tree.eraseClass(x);
+tree.eraseClass(y);
 }
 /// @}

changeset 2031	080d51024ac5
parent 1993	2115143eceea
child 2042	bdc953f2a449