Changeset 1093:31834bad3e84 in lemon-0.x for src/lemon/max_matching.h

Timestamp:

01/25/05 18:40:22 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@1491

Message:

Adding a function which returns the mate of a node.

File:

• src/lemon/max_matching.h (modified) (21 diffs)

src/lemon/max_matching.h

@@ -19 +19 @@
 
 #include <queue>
-#include <invalid.h>
-#include <unionfind.h>
+#include <lemon/invalid.h>
+#include <lemon/unionfind.h>
 #include <lemon/graph_utils.h>
 
@@ -82 +82 @@
     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 +120 @@
     ///
     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.
@@ -129 +137 @@
     void readNMapNode(NMapN& map) {
       for(NodeIt v(g); v!=INVALID; ++v) {
-        mate.set(v,map[v]);   
+        _mate.set(v,map[v]);   
       } 
     } 
@@ -141 +149 @@
     void writeNMapNode (NMapN& map) const {
       for(NodeIt v(g); v!=INVALID; ++v) {
-        map.set(v,mate[v]);   
+        map.set(v,_mate[v]);   
       } 
     } 
@@ -156 +164 @@
         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)); 
       } 
     } 
@@ -170 +178 @@
       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 ) {
@@ -198 +206 @@
           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);
         } 
       } 
@@ -217 +225 @@
       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 ) {
@@ -293 +301 @@
 
     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); 
@@ -334 +342 @@
           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
         
@@ -391 +399 @@
             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
         
@@ -416 +424 @@
           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); 
@@ -430 +438 @@
           } 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 
@@ -444 +452 @@
   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;
           }
@@ -460 +468 @@
     int s=0;
     for(NodeIt v(g); v!=INVALID; ++v) {
-      if ( mate[v]!=INVALID ) {
+      if ( _mate[v]!=INVALID ) {
         ++s;
       }
@@ -470 +478 @@
   void MaxMatching<Graph>::resetMatching() {
     for(NodeIt v(g); v!=INVALID; ++v)
-      mate.set(v,INVALID);      
+      _mate.set(v,INVALID);      
   }
 
@@ -480 +488 @@
         
       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);
@@ -493 +501 @@
         } 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;
         }
@@ -508 +516 @@
     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);
@@ -528 +536 @@
   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;