Adding a function which returns the mate of a node.
authorjacint
Tue, 25 Jan 2005 17:40:22 +0000
changeset 109331834bad3e84
parent 1092 36284b2500c3
child 1094 da32bccc7c4d
Adding a function which returns the mate of a node.
src/lemon/max_matching.h
     1.1 --- a/src/lemon/max_matching.h	Tue Jan 25 17:39:24 2005 +0000
     1.2 +++ b/src/lemon/max_matching.h	Tue Jan 25 17:40:22 2005 +0000
     1.3 @@ -18,8 +18,8 @@
     1.4  #define LEMON_MAX_MATCHING_H
     1.5  
     1.6  #include <queue>
     1.7 -#include <invalid.h>
     1.8 -#include <unionfind.h>
     1.9 +#include <lemon/invalid.h>
    1.10 +#include <lemon/unionfind.h>
    1.11  #include <lemon/graph_utils.h>
    1.12  
    1.13  ///\ingroup galgs
    1.14 @@ -81,12 +81,12 @@
    1.15  
    1.16      static const int HEUR_density=2;
    1.17      const Graph& g;
    1.18 -    typename Graph::template NodeMap<Node> mate;
    1.19 +    typename Graph::template NodeMap<Node> _mate;
    1.20      typename Graph::template NodeMap<pos_enum> position;
    1.21       
    1.22    public:
    1.23      
    1.24 -    MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g) {}
    1.25 +    MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {}
    1.26  
    1.27      ///Runs Edmonds' algorithm.
    1.28  
    1.29 @@ -120,6 +120,14 @@
    1.30      ///
    1.31      void resetMatching();
    1.32  
    1.33 +    ///Returns the mate of a node in the actual matching.
    1.34 +
    1.35 +    ///Returns the mate of a \c node in the actual matching. 
    1.36 +    ///Returns INVALID if the \c node is not covered by the actual matching. 
    1.37 +    Node mate(Node& node) const {
    1.38 +      return _mate[node];
    1.39 +    } 
    1.40 +
    1.41      ///Reads a matching from a \c Node map of \c Nodes.
    1.42  
    1.43      ///Reads a matching from a \c Node map of \c Nodes. This map must be \e
    1.44 @@ -128,7 +136,7 @@
    1.45      template<typename NMapN>
    1.46      void readNMapNode(NMapN& map) {
    1.47        for(NodeIt v(g); v!=INVALID; ++v) {
    1.48 -	mate.set(v,map[v]);   
    1.49 +	_mate.set(v,map[v]);   
    1.50        } 
    1.51      } 
    1.52      
    1.53 @@ -140,7 +148,7 @@
    1.54      template<typename NMapN>
    1.55      void writeNMapNode (NMapN& map) const {
    1.56        for(NodeIt v(g); v!=INVALID; ++v) {
    1.57 -	map.set(v,mate[v]);   
    1.58 +	map.set(v,_mate[v]);   
    1.59        } 
    1.60      } 
    1.61  
    1.62 @@ -155,7 +163,7 @@
    1.63       for(NodeIt v(g); v!=INVALID; ++v) {
    1.64  	Edge e=map[v];
    1.65  	if ( g.valid(e) )
    1.66 -	  g.source(e) == v ? mate.set(v,g.target(e)) : mate.set(v,g.source(e)); 
    1.67 +	  g.source(e) == v ? _mate.set(v,g.target(e)) : _mate.set(v,g.source(e)); 
    1.68        } 
    1.69      } 
    1.70      
    1.71 @@ -169,8 +177,8 @@
    1.72      void writeNMapEdge (NMapE& map)  const {
    1.73        typename Graph::template NodeMap<bool> todo(g,true); 
    1.74        for(NodeIt v(g); v!=INVALID; ++v) {
    1.75 -	if ( todo[v] && mate[v]!=INVALID ) {
    1.76 -	  Node u=mate[v];
    1.77 +	if ( todo[v] && _mate[v]!=INVALID ) {
    1.78 +	  Node u=_mate[v];
    1.79  	  for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
    1.80  	    if ( g.target(e) == u ) {
    1.81  	      map.set(u,e);
    1.82 @@ -197,8 +205,8 @@
    1.83  	if ( map[e] ) {
    1.84  	  Node u=g.source(e);	  
    1.85  	  Node v=g.target(e);
    1.86 -	  mate.set(u,v);
    1.87 -	  mate.set(v,u);
    1.88 +	  _mate.set(u,v);
    1.89 +	  _mate.set(v,u);
    1.90  	} 
    1.91        } 
    1.92      }
    1.93 @@ -216,8 +224,8 @@
    1.94  
    1.95        typename Graph::template NodeMap<bool> todo(g,true); 
    1.96        for(NodeIt v(g); v!=INVALID; ++v) {
    1.97 -	if ( todo[v] && mate[v]!=INVALID ) {
    1.98 -	  Node u=mate[v];
    1.99 +	if ( todo[v] && _mate[v]!=INVALID ) {
   1.100 +	  Node u=_mate[v];
   1.101  	  for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
   1.102  	    if ( g.target(e) == u ) {
   1.103  	      map.set(e,true);
   1.104 @@ -292,7 +300,7 @@
   1.105      UFE tree(tree_base);
   1.106  
   1.107      for(NodeIt v(g); v!=INVALID; ++v) {
   1.108 -      if ( position[v]==C && mate[v]==INVALID ) {
   1.109 +      if ( position[v]==C && _mate[v]==INVALID ) {
   1.110  	blossom.insert(v);
   1.111  	tree.insert(v); 
   1.112  	position.set(v,D);
   1.113 @@ -333,11 +341,11 @@
   1.114  
   1.115  	  Node b=blossom.find(x);
   1.116  	  path.set(b,true);
   1.117 -	  b=mate[b];
   1.118 +	  b=_mate[b];
   1.119  	  while ( b!=INVALID ) { 
   1.120  	    b=blossom.find(ear[b]);
   1.121  	    path.set(b,true);
   1.122 -	    b=mate[b];
   1.123 +	    b=_mate[b];
   1.124  	  } //going till the root
   1.125  	
   1.126  	  Node top=y;
   1.127 @@ -390,11 +398,11 @@
   1.128  	      
   1.129  	    Node b=blossom.find(x);
   1.130  	    path.set(b,true);
   1.131 -	    b=mate[b];
   1.132 +	    b=_mate[b];
   1.133  	    while ( b!=INVALID ) { 
   1.134  	      b=blossom.find(ear[b]);
   1.135  	      path.set(b,true);
   1.136 -	      b=mate[b];
   1.137 +	      b=_mate[b];
   1.138  	    } //going till the root
   1.139  	
   1.140  	    Node top=y;
   1.141 @@ -415,10 +423,10 @@
   1.142  	  }
   1.143  	  break;
   1.144  	case C:
   1.145 -	  if ( mate[y]!=INVALID ) {   //grow
   1.146 +	  if ( _mate[y]!=INVALID ) {   //grow
   1.147  
   1.148  	    ear.set(y,x);
   1.149 -	    Node w=mate[y];
   1.150 +	    Node w=_mate[y];
   1.151  	    blossom.insert(w);
   1.152  	    position.set(y,A); 
   1.153  	    position.set(w,D); 
   1.154 @@ -429,8 +437,8 @@
   1.155  	    Q.push(w);
   1.156  	  } else {                 //augment  
   1.157  	    augment(x, ear, blossom, tree);
   1.158 -	    mate.set(x,y);
   1.159 -	    mate.set(y,x);
   1.160 +	    _mate.set(x,y);
   1.161 +	    _mate.set(y,x);
   1.162  	    return;
   1.163  	  } //if 
   1.164  	  break;
   1.165 @@ -443,12 +451,12 @@
   1.166    template <typename Graph>
   1.167    void MaxMatching<Graph>::greedyMatching() {
   1.168      for(NodeIt v(g); v!=INVALID; ++v)
   1.169 -      if ( mate[v]==INVALID ) {
   1.170 +      if ( _mate[v]==INVALID ) {
   1.171  	for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
   1.172  	  Node y=g.target(e);
   1.173 -	  if ( mate[y]==INVALID && y!=v ) {
   1.174 -	    mate.set(v,y);
   1.175 -	    mate.set(y,v);
   1.176 +	  if ( _mate[y]==INVALID && y!=v ) {
   1.177 +	    _mate.set(v,y);
   1.178 +	    _mate.set(y,v);
   1.179  	    break;
   1.180  	  }
   1.181  	}
   1.182 @@ -459,7 +467,7 @@
   1.183    int MaxMatching<Graph>::size() const {
   1.184      int s=0;
   1.185      for(NodeIt v(g); v!=INVALID; ++v) {
   1.186 -      if ( mate[v]!=INVALID ) {
   1.187 +      if ( _mate[v]!=INVALID ) {
   1.188  	++s;
   1.189        }
   1.190      }
   1.191 @@ -469,7 +477,7 @@
   1.192    template <typename Graph>
   1.193    void MaxMatching<Graph>::resetMatching() {
   1.194      for(NodeIt v(g); v!=INVALID; ++v)
   1.195 -      mate.set(v,INVALID);      
   1.196 +      _mate.set(v,INVALID);      
   1.197    }
   1.198  
   1.199    template <typename Graph>
   1.200 @@ -479,9 +487,9 @@
   1.201        Node y=g.target(e);
   1.202  	
   1.203        if ( position[y]==C ) {
   1.204 -	if ( mate[y]!=INVALID ) {       //grow
   1.205 +	if ( _mate[y]!=INVALID ) {       //grow
   1.206  	  ear.set(y,x);
   1.207 -	  Node w=mate[y];
   1.208 +	  Node w=_mate[y];
   1.209  	  blossom.insert(w);
   1.210  	  position.set(y,A);
   1.211  	  position.set(w,D);
   1.212 @@ -492,8 +500,8 @@
   1.213  	  Q.push(w);
   1.214  	} else {                      //augment 
   1.215  	  augment(x, ear, blossom, tree);
   1.216 -	  mate.set(x,y);
   1.217 -	  mate.set(y,x);
   1.218 +	  _mate.set(x,y);
   1.219 +	  _mate.set(y,x);
   1.220  	  return true;
   1.221  	}
   1.222        }
   1.223 @@ -507,11 +515,11 @@
   1.224      ear.set(top,bottom);
   1.225      Node t=top;
   1.226      while ( t!=middle ) {
   1.227 -      Node u=mate[t];
   1.228 +      Node u=_mate[t];
   1.229        t=ear[u];
   1.230        ear.set(t,u);
   1.231      } 
   1.232 -    bottom=mate[middle];
   1.233 +    bottom=_mate[middle];
   1.234      position.set(bottom,D);
   1.235      Q.push(bottom);
   1.236      top=ear[bottom];		
   1.237 @@ -527,14 +535,14 @@
   1.238    template <typename Graph>
   1.239    void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear,  
   1.240  				   UFE& blossom, UFE& tree) { 
   1.241 -    Node v=mate[x];
   1.242 +    Node v=_mate[x];
   1.243      while ( v!=INVALID ) {
   1.244  	
   1.245        Node u=ear[v];
   1.246 -      mate.set(v,u);
   1.247 +      _mate.set(v,u);
   1.248        Node tmp=v;
   1.249 -      v=mate[u];
   1.250 -      mate.set(u,tmp);
   1.251 +      v=_mate[u];
   1.252 +      _mate.set(u,tmp);
   1.253      }
   1.254      typename UFE::ItemIt it;
   1.255      for (tree.first(it,blossom.find(x)); tree.valid(it); tree.next(it)) {