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)) {