COIN-OR::LEMON - Graph Library

Changeset 1587:8f1c317ebeb4 in lemon-0.x for lemon/max_matching.h


Ignore:
Timestamp:
07/26/05 15:15:13 (14 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2091
Message:

Doc improvements

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/max_matching.h

    r1435 r1587  
    9898    ///2*number of nodes), and a heuristical Edmonds' algorithm with a
    9999    ///heuristic of postponing shrinks for dense graphs.
    100     inline void run();
     100    void run() {
     101      if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
     102        greedyMatching();
     103        runEdmonds(0);
     104      } else runEdmonds(1);
     105    }
     106
    101107
    102108    ///Runs Edmonds' algorithm.
     
    105111    ///Edmonds' algorithm with a heuristic of postponing shrinks,
    106112    ///giving a faster algorithm for dense graphs. 
    107     void runEdmonds( int heur );
     113    void runEdmonds( int heur = 1 ) {
     114     
     115      for(NodeIt v(g); v!=INVALID; ++v)
     116        position.set(v,C);     
     117     
     118      typename Graph::template NodeMap<Node> ear(g,INVALID);
     119      //undefined for the base nodes of the blossoms (i.e. for the
     120      //representative elements of UFE blossom) and for the nodes in C
     121     
     122      typename UFE::MapType blossom_base(g);
     123      UFE blossom(blossom_base);
     124      typename UFE::MapType tree_base(g);
     125      UFE tree(tree_base);
     126      //If these UFE's would be members of the class then also
     127      //blossom_base and tree_base should be a member.
     128     
     129      for(NodeIt v(g); v!=INVALID; ++v) {
     130        if ( position[v]==C && _mate[v]==INVALID ) {
     131          blossom.insert(v);
     132          tree.insert(v);
     133          position.set(v,D);
     134          if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
     135          else normShrink( v, ear, blossom, tree );
     136        }
     137      }
     138    }
     139
    108140
    109141    ///Finds a greedy matching starting from the actual matching.
     
    111143    ///Starting form the actual matching stored, it finds a maximal
    112144    ///greedy matching.
    113     void greedyMatching();
     145    void greedyMatching() {
     146      for(NodeIt v(g); v!=INVALID; ++v)
     147        if ( _mate[v]==INVALID ) {
     148          for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
     149            Node y=g.runningNode(e);
     150            if ( _mate[y]==INVALID && y!=v ) {
     151              _mate.set(v,y);
     152              _mate.set(y,v);
     153              break;
     154            }
     155          }
     156        }
     157    }
    114158
    115159    ///Returns the size of the actual matching stored.
     
    117161    ///Returns the size of the actual matching stored. After \ref
    118162    ///run() it returns the size of a maximum matching in the graph.
    119     int size() const;
     163    int size() const {
     164      int s=0;
     165      for(NodeIt v(g); v!=INVALID; ++v) {
     166        if ( _mate[v]!=INVALID ) {
     167          ++s;
     168        }
     169      }
     170      return s/2;
     171    }
     172
    120173
    121174    ///Resets the actual matching to the empty matching.
     
    123176    ///Resets the actual matching to the empty matching. 
    124177    ///
    125     void resetMatching();
     178    void resetMatching() {
     179      for(NodeIt v(g); v!=INVALID; ++v)
     180        _mate.set(v,INVALID);     
     181    }
    126182
    127183    ///Returns the mate of a node in the actual matching.
     
    285341
    286342  template <typename Graph>
    287   void MaxMatching<Graph>::run() {
    288     if ( countUndirEdges(g) < HEUR_density*countNodes(g) ) {
    289       greedyMatching();
    290       runEdmonds(0);
    291     } else runEdmonds(1);
    292   }
    293 
    294 
    295   template <typename Graph>
    296   void MaxMatching<Graph>::runEdmonds( int heur=1 ) {
    297 
    298     for(NodeIt v(g); v!=INVALID; ++v)
    299       position.set(v,C);     
    300 
    301     typename Graph::template NodeMap<Node> ear(g,INVALID);
    302     //undefined for the base nodes of the blossoms (i.e. for the
    303     //representative elements of UFE blossom) and for the nodes in C
    304 
    305     typename UFE::MapType blossom_base(g);
    306     UFE blossom(blossom_base);
    307     typename UFE::MapType tree_base(g);
    308     UFE tree(tree_base);
    309     //If these UFE's would be members of the class then also
    310     //blossom_base and tree_base should be a member.
    311 
    312     for(NodeIt v(g); v!=INVALID; ++v) {
    313       if ( position[v]==C && _mate[v]==INVALID ) {
    314         blossom.insert(v);
    315         tree.insert(v);
    316         position.set(v,D);
    317         if ( heur == 1 ) lateShrink( v, ear, blossom, tree );
    318         else normShrink( v, ear, blossom, tree );
    319       }
    320     }
    321   }
    322 
    323    
    324   template <typename Graph>
    325343  void MaxMatching<Graph>::lateShrink(Node v, typename Graph::template NodeMap<Node>& ear, 
    326344                                      UFE& blossom, UFE& tree) {
     
    458476      }
    459477    }
    460   }
    461 
    462   template <typename Graph>
    463   void MaxMatching<Graph>::greedyMatching() {
    464     for(NodeIt v(g); v!=INVALID; ++v)
    465       if ( _mate[v]==INVALID ) {
    466         for( IncEdgeIt e(g,v); e!=INVALID ; ++e ) {
    467           Node y=g.runningNode(e);
    468           if ( _mate[y]==INVALID && y!=v ) {
    469             _mate.set(v,y);
    470             _mate.set(y,v);
    471             break;
    472           }
    473         }
    474       }
    475   }
    476    
    477   template <typename Graph>
    478   int MaxMatching<Graph>::size() const {
    479     int s=0;
    480     for(NodeIt v(g); v!=INVALID; ++v) {
    481       if ( _mate[v]!=INVALID ) {
    482         ++s;
    483       }
    484     }
    485     return s/2;
    486   }
    487 
    488   template <typename Graph>
    489   void MaxMatching<Graph>::resetMatching() {
    490     for(NodeIt v(g); v!=INVALID; ++v)
    491       _mate.set(v,INVALID);     
    492478  }
    493479
Note: See TracChangeset for help on using the changeset viewer.