COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
01/25/05 18:40:22 (19 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:
1 edited

Legend:

Unmodified
Added
Removed
  • src/lemon/max_matching.h

    r1090 r1093  
    1919
    2020#include <queue>
    21 #include <invalid.h>
    22 #include <unionfind.h>
     21#include <lemon/invalid.h>
     22#include <lemon/unionfind.h>
    2323#include <lemon/graph_utils.h>
    2424
     
    8282    static const int HEUR_density=2;
    8383    const Graph& g;
    84     typename Graph::template NodeMap<Node> mate;
     84    typename Graph::template NodeMap<Node> _mate;
    8585    typename Graph::template NodeMap<pos_enum> position;
    8686     
    8787  public:
    8888   
    89     MaxMatching(const Graph& _g) : g(_g), mate(_g,INVALID), position(_g) {}
     89    MaxMatching(const Graph& _g) : g(_g), _mate(_g,INVALID), position(_g) {}
    9090
    9191    ///Runs Edmonds' algorithm.
     
    120120    ///
    121121    void resetMatching();
     122
     123    ///Returns the mate of a node in the actual matching.
     124
     125    ///Returns the mate of a \c node in the actual matching.
     126    ///Returns INVALID if the \c node is not covered by the actual matching.
     127    Node mate(Node& node) const {
     128      return _mate[node];
     129    }
    122130
    123131    ///Reads a matching from a \c Node map of \c Nodes.
     
    129137    void readNMapNode(NMapN& map) {
    130138      for(NodeIt v(g); v!=INVALID; ++v) {
    131         mate.set(v,map[v]);   
     139        _mate.set(v,map[v]);   
    132140      }
    133141    }
     
    141149    void writeNMapNode (NMapN& map) const {
    142150      for(NodeIt v(g); v!=INVALID; ++v) {
    143         map.set(v,mate[v]);   
     151        map.set(v,_mate[v]);   
    144152      }
    145153    }
     
    156164        Edge e=map[v];
    157165        if ( g.valid(e) )
    158           g.source(e) == v ? mate.set(v,g.target(e)) : mate.set(v,g.source(e));
     166          g.source(e) == v ? _mate.set(v,g.target(e)) : _mate.set(v,g.source(e));
    159167      }
    160168    }
     
    170178      typename Graph::template NodeMap<bool> todo(g,true);
    171179      for(NodeIt v(g); v!=INVALID; ++v) {
    172         if ( todo[v] && mate[v]!=INVALID ) {
    173           Node u=mate[v];
     180        if ( todo[v] && _mate[v]!=INVALID ) {
     181          Node u=_mate[v];
    174182          for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
    175183            if ( g.target(e) == u ) {
     
    198206          Node u=g.source(e);     
    199207          Node v=g.target(e);
    200           mate.set(u,v);
    201           mate.set(v,u);
     208          _mate.set(u,v);
     209          _mate.set(v,u);
    202210        }
    203211      }
     
    217225      typename Graph::template NodeMap<bool> todo(g,true);
    218226      for(NodeIt v(g); v!=INVALID; ++v) {
    219         if ( todo[v] && mate[v]!=INVALID ) {
    220           Node u=mate[v];
     227        if ( todo[v] && _mate[v]!=INVALID ) {
     228          Node u=_mate[v];
    221229          for(IncEdgeIt e(g,v); e!=INVALID; ++e) {
    222230            if ( g.target(e) == u ) {
     
    293301
    294302    for(NodeIt v(g); v!=INVALID; ++v) {
    295       if ( position[v]==C && mate[v]==INVALID ) {
     303      if ( position[v]==C && _mate[v]==INVALID ) {
    296304        blossom.insert(v);
    297305        tree.insert(v);
     
    334342          Node b=blossom.find(x);
    335343          path.set(b,true);
    336           b=mate[b];
     344          b=_mate[b];
    337345          while ( b!=INVALID ) {
    338346            b=blossom.find(ear[b]);
    339347            path.set(b,true);
    340             b=mate[b];
     348            b=_mate[b];
    341349          } //going till the root
    342350       
     
    391399            Node b=blossom.find(x);
    392400            path.set(b,true);
    393             b=mate[b];
     401            b=_mate[b];
    394402            while ( b!=INVALID ) {
    395403              b=blossom.find(ear[b]);
    396404              path.set(b,true);
    397               b=mate[b];
     405              b=_mate[b];
    398406            } //going till the root
    399407       
     
    416424          break;
    417425        case C:
    418           if ( mate[y]!=INVALID ) {   //grow
     426          if ( _mate[y]!=INVALID ) {   //grow
    419427
    420428            ear.set(y,x);
    421             Node w=mate[y];
     429            Node w=_mate[y];
    422430            blossom.insert(w);
    423431            position.set(y,A);
     
    430438          } else {                 //augment 
    431439            augment(x, ear, blossom, tree);
    432             mate.set(x,y);
    433             mate.set(y,x);
     440            _mate.set(x,y);
     441            _mate.set(y,x);
    434442            return;
    435443          } //if
     
    444452  void MaxMatching<Graph>::greedyMatching() {
    445453    for(NodeIt v(g); v!=INVALID; ++v)
    446       if ( mate[v]==INVALID ) {
     454      if ( _mate[v]==INVALID ) {
    447455        for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
    448456          Node y=g.target(e);
    449           if ( mate[y]==INVALID && y!=v ) {
    450             mate.set(v,y);
    451             mate.set(y,v);
     457          if ( _mate[y]==INVALID && y!=v ) {
     458            _mate.set(v,y);
     459            _mate.set(y,v);
    452460            break;
    453461          }
     
    460468    int s=0;
    461469    for(NodeIt v(g); v!=INVALID; ++v) {
    462       if ( mate[v]!=INVALID ) {
     470      if ( _mate[v]!=INVALID ) {
    463471        ++s;
    464472      }
     
    470478  void MaxMatching<Graph>::resetMatching() {
    471479    for(NodeIt v(g); v!=INVALID; ++v)
    472       mate.set(v,INVALID);     
     480      _mate.set(v,INVALID);     
    473481  }
    474482
     
    480488       
    481489      if ( position[y]==C ) {
    482         if ( mate[y]!=INVALID ) {       //grow
     490        if ( _mate[y]!=INVALID ) {       //grow
    483491          ear.set(y,x);
    484           Node w=mate[y];
     492          Node w=_mate[y];
    485493          blossom.insert(w);
    486494          position.set(y,A);
     
    493501        } else {                      //augment
    494502          augment(x, ear, blossom, tree);
    495           mate.set(x,y);
    496           mate.set(y,x);
     503          _mate.set(x,y);
     504          _mate.set(y,x);
    497505          return true;
    498506        }
     
    508516    Node t=top;
    509517    while ( t!=middle ) {
    510       Node u=mate[t];
     518      Node u=_mate[t];
    511519      t=ear[u];
    512520      ear.set(t,u);
    513521    }
    514     bottom=mate[middle];
     522    bottom=_mate[middle];
    515523    position.set(bottom,D);
    516524    Q.push(bottom);
     
    528536  void MaxMatching<Graph>::augment(Node x, typename Graph::NodeMap<Node>& ear, 
    529537                                   UFE& blossom, UFE& tree) {
    530     Node v=mate[x];
     538    Node v=_mate[x];
    531539    while ( v!=INVALID ) {
    532540       
    533541      Node u=ear[v];
    534       mate.set(v,u);
     542      _mate.set(v,u);
    535543      Node tmp=v;
    536       v=mate[u];
    537       mate.set(u,tmp);
     544      v=_mate[u];
     545      _mate.set(u,tmp);
    538546    }
    539547    typename UFE::ItemIt it;
Note: See TracChangeset for help on using the changeset viewer.