# HG changeset patch
# User jacint
# Date 1106674822 0
# Node ID 31834bad3e84e35091720268c7dba50722959669
# Parent  36284b2500c326f2c5fd2a4f7b61020ae2d40a15
Adding a function which returns the mate of a node.

diff -r 36284b2500c3 -r 31834bad3e84 src/lemon/max_matching.h
--- a/src/lemon/max_matching.h	Tue Jan 25 17:39:24 2005 +0000
+++ b/src/lemon/max_matching.h	Tue Jan 25 17:40:22 2005 +0000
@@ -18,8 +18,8 @@
 #define LEMON_MAX_MATCHING_H
 
 #include <queue>
-#include <invalid.h>
-#include <unionfind.h>
+#include <lemon/invalid.h>
+#include <lemon/unionfind.h>
 #include <lemon/graph_utils.h>
 
 ///\ingroup galgs
@@ -81,12 +81,12 @@
 
     static const int HEUR_density=2;
     const Graph& g;
-    typename Graph::template NodeMap<Node> mate;
+    typename Graph::template NodeMap<Node> _mate;
     typename Graph::template NodeMap<pos_enum> position;
      
   public:
     
-    MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g) {}
+    MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {}
 
     ///Runs Edmonds' algorithm.
 
@@ -120,6 +120,14 @@
     ///
     void resetMatching();
 
+    ///Returns the mate of a node in the actual matching.
+
+    ///Returns the mate of a \c node in the actual matching. 
+    ///Returns INVALID if the \c node is not covered by the actual matching. 
+    Node mate(Node& node) const {
+      return _mate[node];
+    } 
+
     ///Reads a matching from a \c Node map of \c Nodes.
 
     ///Reads a matching from a \c Node map of \c Nodes. This map must be \e
@@ -128,7 +136,7 @@
     template<typename NMapN>
     void readNMapNode(NMapN& map) {
       for(NodeIt v(g); v!=INVALID; ++v) {
-	mate.set(v,map[v]);   
+	_mate.set(v,map[v]);   
       } 
     } 
     
@@ -140,7 +148,7 @@
     template<typename NMapN>
     void writeNMapNode (NMapN& map) const {
       for(NodeIt v(g); v!=INVALID; ++v) {
-	map.set(v,mate[v]);   
+	map.set(v,_mate[v]);   
       } 
     } 
 
@@ -155,7 +163,7 @@
      for(NodeIt v(g); v!=INVALID; ++v) {
 	Edge e=map[v];
 	if ( g.valid(e) )
-	  g.source(e) == v ? mate.set(v,g.target(e)) : mate.set(v,g.source(e)); 
+	  g.source(e) == v ? _mate.set(v,g.target(e)) : _mate.set(v,g.source(e)); 
       } 
     } 
     
@@ -169,8 +177,8 @@
     void writeNMapEdge (NMapE& map)  const {
       typename Graph::template NodeMap<bool> todo(g,true); 
       for(NodeIt v(g); v!=INVALID; ++v) {
-	if ( todo[v] && mate[v]!=INVALID ) {
-	  Node u=mate[v];
+	if ( todo[v] && _mate[v]!=INVALID ) {
+	  Node u=_mate[v];
 	  for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
 	    if ( g.target(e) == u ) {
 	      map.set(u,e);
@@ -197,8 +205,8 @@
 	if ( map[e] ) {
 	  Node u=g.source(e);	  
 	  Node v=g.target(e);
-	  mate.set(u,v);
-	  mate.set(v,u);
+	  _mate.set(u,v);
+	  _mate.set(v,u);
 	} 
       } 
     }
@@ -216,8 +224,8 @@
 
       typename Graph::template NodeMap<bool> todo(g,true); 
       for(NodeIt v(g); v!=INVALID; ++v) {
-	if ( todo[v] && mate[v]!=INVALID ) {
-	  Node u=mate[v];
+	if ( todo[v] && _mate[v]!=INVALID ) {
+	  Node u=_mate[v];
 	  for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
 	    if ( g.target(e) == u ) {
 	      map.set(e,true);
@@ -292,7 +300,7 @@
     UFE tree(tree_base);
 
     for(NodeIt v(g); v!=INVALID; ++v) {
-      if ( position[v]==C && mate[v]==INVALID ) {
+      if ( position[v]==C && _mate[v]==INVALID ) {
 	blossom.insert(v);
 	tree.insert(v); 
 	position.set(v,D);
@@ -333,11 +341,11 @@
 
 	  Node b=blossom.find(x);
 	  path.set(b,true);
-	  b=mate[b];
+	  b=_mate[b];
 	  while ( b!=INVALID ) { 
 	    b=blossom.find(ear[b]);
 	    path.set(b,true);
-	    b=mate[b];
+	    b=_mate[b];
 	  } //going till the root
 	
 	  Node top=y;
@@ -390,11 +398,11 @@
 	      
 	    Node b=blossom.find(x);
 	    path.set(b,true);
-	    b=mate[b];
+	    b=_mate[b];
 	    while ( b!=INVALID ) { 
 	      b=blossom.find(ear[b]);
 	      path.set(b,true);
-	      b=mate[b];
+	      b=_mate[b];
 	    } //going till the root
 	
 	    Node top=y;
@@ -415,10 +423,10 @@
 	  }
 	  break;
 	case C:
-	  if ( mate[y]!=INVALID ) {   //grow
+	  if ( _mate[y]!=INVALID ) {   //grow
 
 	    ear.set(y,x);
-	    Node w=mate[y];
+	    Node w=_mate[y];
 	    blossom.insert(w);
 	    position.set(y,A); 
 	    position.set(w,D); 
@@ -429,8 +437,8 @@
 	    Q.push(w);
 	  } else {                 //augment  
 	    augment(x, ear, blossom, tree);
-	    mate.set(x,y);
-	    mate.set(y,x);
+	    _mate.set(x,y);
+	    _mate.set(y,x);
 	    return;
 	  } //if 
 	  break;
@@ -443,12 +451,12 @@
   template <typename Graph>
   void MaxMatching<Graph>::greedyMatching() {
     for(NodeIt v(g); v!=INVALID; ++v)
-      if ( mate[v]==INVALID ) {
+      if ( _mate[v]==INVALID ) {
 	for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
 	  Node y=g.target(e);
-	  if ( mate[y]==INVALID && y!=v ) {
-	    mate.set(v,y);
-	    mate.set(y,v);
+	  if ( _mate[y]==INVALID && y!=v ) {
+	    _mate.set(v,y);
+	    _mate.set(y,v);
 	    break;
 	  }
 	}
@@ -459,7 +467,7 @@
   int MaxMatching<Graph>::size() const {
     int s=0;
     for(NodeIt v(g); v!=INVALID; ++v) {
-      if ( mate[v]!=INVALID ) {
+      if ( _mate[v]!=INVALID ) {
 	++s;
       }
     }
@@ -469,7 +477,7 @@
   template <typename Graph>
   void MaxMatching<Graph>::resetMatching() {
     for(NodeIt v(g); v!=INVALID; ++v)
-      mate.set(v,INVALID);      
+      _mate.set(v,INVALID);      
   }
 
   template <typename Graph>
@@ -479,9 +487,9 @@
       Node y=g.target(e);
 	
       if ( position[y]==C ) {
-	if ( mate[y]!=INVALID ) {       //grow
+	if ( _mate[y]!=INVALID ) {       //grow
 	  ear.set(y,x);
-	  Node w=mate[y];
+	  Node w=_mate[y];
 	  blossom.insert(w);
 	  position.set(y,A);
 	  position.set(w,D);
@@ -492,8 +500,8 @@
 	  Q.push(w);
 	} else {                      //augment 
 	  augment(x, ear, blossom, tree);
-	  mate.set(x,y);
-	  mate.set(y,x);
+	  _mate.set(x,y);
+	  _mate.set(y,x);
 	  return true;
 	}
       }
@@ -507,11 +515,11 @@
     ear.set(top,bottom);
     Node t=top;
     while ( t!=middle ) {
-      Node u=mate[t];
+      Node u=_mate[t];
       t=ear[u];
       ear.set(t,u);
     } 
-    bottom=mate[middle];
+    bottom=_mate[middle];
     position.set(bottom,D);
     Q.push(bottom);
     top=ear[bottom];		
@@ -527,14 +535,14 @@
   template <typename Graph>
   void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear,  
 				   UFE& blossom, UFE& tree) { 
-    Node v=mate[x];
+    Node v=_mate[x];
     while ( v!=INVALID ) {
 	
       Node u=ear[v];
-      mate.set(v,u);
+      _mate.set(v,u);
       Node tmp=v;
-      v=mate[u];
-      mate.set(u,tmp);
+      v=_mate[u];
+      _mate.set(u,tmp);
     }
     typename UFE::ItemIt it;
     for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {