COIN-OR::LEMON - Graph Library

Changeset 2505:1bb471764ab8 in lemon-0.x for test/max_matching_test.cc


Ignore:
Timestamp:
10/30/07 21:21:10 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@3351
Message:

Redesign interface of MaxMatching? and UnionFindEnum?
New class ExtendFindEnum?

Faster MaxMatching?

File:
1 edited

Legend:

Unmodified
Added
Removed
  • test/max_matching_test.cc

    r2391 r2505  
    6767 
    6868  MaxMatching<Graph> max_matching(g);
    69   max_matching.runEdmonds(0);
     69  max_matching.init();
     70  max_matching.startDense();
    7071 
    7172  int s=0;
    7273  Graph::NodeMap<Node> mate(g,INVALID);
    73   max_matching.writeNMapNode(mate);
     74  max_matching.mateMap(mate);
    7475  for(NodeIt v(g); v!=INVALID; ++v) {
    7576    if ( mate[v]!=INVALID ) ++s;
     
    8384  check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
    8485
    85   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(g);
    86   max_matching.writePos(pos0);
     86  Graph::NodeMap<MaxMatching<Graph>::DecompType> pos0(g);
     87  max_matching.decomposition(pos0);
    8788 
    88   max_matching.resetMatching();
    89   max_matching.runEdmonds(1);
     89  max_matching.init();
     90  max_matching.startSparse();
    9091  s=0;
    91   max_matching.writeNMapNode(mate);
     92  max_matching.mateMap(mate);
    9293  for(NodeIt v(g); v!=INVALID; ++v) {
    9394    if ( mate[v]!=INVALID ) ++s;
     
    9596  check ( int(s/2) == size, "The size does not equal!" );
    9697
    97   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
    98   max_matching.writePos(pos1);
     98  Graph::NodeMap<MaxMatching<Graph>::DecompType> pos1(g);
     99  max_matching.decomposition(pos1);
    99100
    100101  max_matching.run();
    101102  s=0;
    102   max_matching.writeNMapNode(mate);
     103  max_matching.mateMap(mate);
    103104  for(NodeIt v(g); v!=INVALID; ++v) {
    104105    if ( mate[v]!=INVALID ) ++s;
     
    106107  check ( int(s/2) == size, "The size does not equal!" );
    107108 
    108   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
    109   max_matching.writePos(pos2);
     109  Graph::NodeMap<MaxMatching<Graph>::DecompType> pos2(g);
     110  max_matching.decomposition(pos2);
    110111
    111   max_matching.resetMatching();
    112112  max_matching.run();
    113113  s=0;
    114   max_matching.writeNMapNode(mate);
     114  max_matching.mateMap(mate);
    115115  for(NodeIt v(g); v!=INVALID; ++v) {
    116116    if ( mate[v]!=INVALID ) ++s;
     
    118118  check ( int(s/2) == size, "The size does not equal!" );
    119119 
    120   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g);
    121   max_matching.writePos(pos);
     120  Graph::NodeMap<MaxMatching<Graph>::DecompType> pos(g);
     121  max_matching.decomposition(pos);
    122122   
    123123  bool ismatching=true;
     
    140140  bool noedge=true;
    141141  for(UEdgeIt e(g); e!=INVALID; ++e) {
    142    if ( (pos[g.target(e)]==max_matching.C && pos[g.source(e)]==max_matching.D) ||
    143          (pos[g.target(e)]==max_matching.D && pos[g.source(e)]==max_matching.C) )
     142   if ( (pos[g.target(e)]==max_matching.C &&
     143         pos[g.source(e)]==max_matching.D) ||
     144         (pos[g.target(e)]==max_matching.D &&
     145          pos[g.source(e)]==max_matching.C) )
    144146      noedge=false;
    145147  }
Note: See TracChangeset for help on using the changeset viewer.