src/work/jacint/max_matching.cc
author marci
Thu, 06 May 2004 15:24:42 +0000
changeset 552 83c22ca968d8
child 921 818510fa3d99
permissions -rw-r--r--
top-sort, for fezso's sake
jacint@536
     1
///Generates a random graph, and tests max_matching.h on it.
jacint@536
     2
#include <iostream>
jacint@536
     3
#include <queue>
jacint@536
     4
#include <math.h>
jacint@536
     5
jacint@536
     6
#include <list_graph.h>
jacint@536
     7
#include <dimacs.h>
jacint@536
     8
#include <graph_gen.h>
jacint@536
     9
#include <max_matching.h>
jacint@536
    10
#include <time_measure.h>
jacint@536
    11
#include <graph_wrapper.h>
jacint@536
    12
jacint@536
    13
using namespace hugo;
jacint@536
    14
jacint@536
    15
int main(int, char **) {
jacint@536
    16
 
jacint@536
    17
  typedef UndirGraph<ListGraph> UGW;
jacint@536
    18
  typedef UGW::Edge Edge;
jacint@536
    19
  typedef UGW::EdgeIt EdgeIt;
jacint@536
    20
  typedef UGW::OutEdgeIt OutEdgeIt;
jacint@536
    21
  typedef UGW::NodeIt NodeIt;
jacint@536
    22
  typedef UGW::Node Node;
jacint@536
    23
   
jacint@536
    24
  UGW G;
jacint@536
    25
jacint@536
    26
  //  random_init(); //If you want to use a random graph with a random
jacint@536
    27
  //  number of edges and nodes.
jacint@536
    28
jacint@536
    29
  int i;
jacint@536
    30
  int j;
jacint@536
    31
  std::cout<<"Number of nodes: ";
jacint@536
    32
  std::cin >> i;
jacint@536
    33
  std::cout<<"Number of edges: ";
jacint@536
    34
  std::cin >> j;
jacint@536
    35
jacint@536
    36
  //  readDimacs(std::cin, G); 
jacint@536
    37
  randomGraph(G, i, j );  
jacint@536
    38
jacint@536
    39
  Timer ts;
jacint@536
    40
  bool noerror=true;
jacint@536
    41
  
jacint@536
    42
  std::cout <<
jacint@536
    43
    "\n  Testing max_matching.h on a random graph with " << 
jacint@536
    44
    G.nodeNum() << " nodes and " << G.edgeNum() << " edges...\n"
jacint@536
    45
	    << std::endl;
jacint@536
    46
  MaxMatching<UGW> max_matching(G);
jacint@536
    47
jacint@536
    48
 
jacint@536
    49
  std::cout << 
jacint@536
    50
    "Running the plain edmonds algorithm runEdmonds(0) using no heuristic... " 
jacint@536
    51
	    <<std::endl;
jacint@536
    52
  ts.reset();  
jacint@536
    53
  max_matching.runEdmonds(0);
jacint@536
    54
  std::cout<<"Elapsed time: "<<ts<<std::endl;
jacint@536
    55
  int s=0;
jacint@536
    56
  UGW::NodeMap<Node> mate(G,INVALID);
jacint@536
    57
  max_matching.writeNMapNode(mate);
jacint@536
    58
  NodeIt v;
jacint@536
    59
  for(G.first(v); G.valid(v); G.next(v) ) {
jacint@536
    60
    if ( G.valid(mate[v]) ) {
jacint@536
    61
      ++s;
jacint@536
    62
    }
jacint@536
    63
  }
jacint@536
    64
  int size=(int)s/2;  //size will be used as the size of a maxmatching
jacint@536
    65
  std::cout << size << " is the size of the matching found by runEdmonds(0),"<<std::endl;
jacint@536
    66
  if ( size == max_matching.size() ) {
jacint@536
    67
    std::cout<< "which equals to the size of the actual matching reported by size().\n"<< std::endl;
jacint@536
    68
  } else {  
jacint@536
    69
    std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl;
jacint@536
    70
    noerror=false;
jacint@536
    71
  }
jacint@536
    72
jacint@536
    73
jacint@536
    74
  std::cout<<"Writing the position by calling writePos...";
jacint@536
    75
  UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos0(G);
jacint@536
    76
  max_matching.writePos(pos0);
jacint@536
    77
  std::cout << "OK" << std::endl;
jacint@536
    78
jacint@536
    79
jacint@536
    80
  std::cout << "Resetting the matching and the position by calling"<< std::endl;
jacint@536
    81
  std::cout<<"resetPos() and resetMatching()...";
jacint@536
    82
  max_matching.resetPos();
jacint@536
    83
  max_matching.resetMatching();
jacint@536
    84
  std::cout <<"OK" << std::endl;
jacint@536
    85
jacint@536
    86
jacint@536
    87
  std::cout << "\nRunning runEdmonds(1) using the 'postpone shrink' heuristic ... " <<std::endl;
jacint@536
    88
  ts.reset();  
jacint@536
    89
  max_matching.runEdmonds(1);
jacint@536
    90
  std::cout<<"Elapsed time: "<<ts<<std::endl;
jacint@536
    91
  s=0;
jacint@536
    92
  max_matching.writeNMapNode(mate);
jacint@536
    93
  for(G.first(v); G.valid(v); G.next(v) ) {
jacint@536
    94
    if ( G.valid(mate[v]) ) {
jacint@536
    95
      ++s;
jacint@536
    96
    }
jacint@536
    97
  }
jacint@536
    98
  std::cout << (int)s/2 << 
jacint@536
    99
    " is the size of the matching found by runEdmonds(1),"<<std::endl;
jacint@536
   100
  if ( (int)s/2 == size ) {
jacint@536
   101
    std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl;
jacint@536
   102
  } else {  
jacint@536
   103
    std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;
jacint@536
   104
    noerror=false;
jacint@536
   105
  } 
jacint@536
   106
  UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos1(G);
jacint@536
   107
  max_matching.writePos(pos1);
jacint@536
   108
jacint@536
   109
jacint@536
   110
  std::cout << "\nStarting run() from the matching given by runEdmonds(1)... " <<std::endl;
jacint@536
   111
  max_matching.resetPos();
jacint@536
   112
  ts.reset();  
jacint@536
   113
  max_matching.run();
jacint@536
   114
  std::cout<<"Elapsed time: "<<ts<<std::endl;
jacint@536
   115
  s=0;
jacint@536
   116
  max_matching.writeNMapNode(mate);
jacint@536
   117
  for(G.first(v); G.valid(v); G.next(v) ) {
jacint@536
   118
    if ( G.valid(mate[v]) ) {
jacint@536
   119
      ++s;
jacint@536
   120
    }
jacint@536
   121
  }
jacint@536
   122
  if ( (int)s/2 == size ) {
jacint@536
   123
    std::cout<< "Found a matching of proper size."<< std::endl;
jacint@536
   124
  } else {  
jacint@536
   125
    std::cout<< "Found a matching of inproper size!"<< std::endl;
jacint@536
   126
    noerror=false;
jacint@536
   127
  }
jacint@536
   128
  UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos2(G);
jacint@536
   129
  max_matching.writePos(pos2);
jacint@536
   130
jacint@536
   131
jacint@536
   132
  std::cout << "\nCalling resetPos() and resetMatching()...";
jacint@536
   133
  max_matching.resetPos();
jacint@536
   134
  max_matching.resetMatching();
jacint@536
   135
  std::cout<<"OK"<<std::endl;
jacint@536
   136
  std::cout <<"Calling greedyMatching() and then runEdmonds(1)... " <<std::endl;
jacint@536
   137
  ts.reset();  
jacint@536
   138
  max_matching.run();
jacint@536
   139
  std::cout<<"Elapsed time: "<<ts<<std::endl;
jacint@536
   140
  s=0;
jacint@536
   141
  max_matching.writeNMapNode(mate);
jacint@536
   142
  for(G.first(v); G.valid(v); G.next(v) ) {
jacint@536
   143
    if ( G.valid(mate[v]) ) {
jacint@536
   144
      ++s;
jacint@536
   145
    }
jacint@536
   146
  }
jacint@536
   147
  std::cout << (int)s/2 << " is the size of the matching found by run(),"<<std::endl;
jacint@536
   148
  if ( (int)s/2 == size ) {
jacint@536
   149
    std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl;
jacint@536
   150
  } else {  
jacint@536
   151
    std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;
jacint@536
   152
    noerror=false;
jacint@536
   153
  }
jacint@536
   154
  UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos(G);
jacint@536
   155
  max_matching.writePos(pos);
jacint@536
   156
   
jacint@536
   157
  
jacint@536
   158
  std::cout<<"\nChecking if the output is a matching...";
jacint@536
   159
  bool ismatching=true;
jacint@536
   160
  for(G.first(v); G.valid(v); G.next(v) )
jacint@536
   161
    if ( G.valid(mate[v]) ) {
jacint@536
   162
      Node u=mate[v];
jacint@536
   163
      if (mate[u]!=v) ismatching=false; 
jacint@536
   164
    }
jacint@536
   165
  if ( ismatching ) std::cout<<"OK"<<std::endl;
jacint@536
   166
  else std::cout<< "It is not a matching!"<< std::endl;
jacint@536
   167
  noerror = noerror && ismatching;
jacint@536
   168
  
jacint@536
   169
jacint@536
   170
  std::cout<<"\nChecking the dual..."<<std::endl;
jacint@536
   171
    
jacint@536
   172
  std::cout<<"Checking if the four position outputs coincide...";
jacint@536
   173
  bool coincide=true;
jacint@536
   174
  int err_node=0;
jacint@536
   175
  for(G.first(v); G.valid(v); G.next(v) ) {
jacint@536
   176
    if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
jacint@536
   177
      ++err_node;
jacint@536
   178
      coincide=false;
jacint@536
   179
    }
jacint@536
   180
  }
jacint@536
   181
  if ( coincide ) std::cout << "OK" <<std::endl;
jacint@536
   182
  else {
jacint@536
   183
    std::cout << "They do not coincide! Number of erroneous nodes: " 
jacint@536
   184
	      << err_node << std::endl;
jacint@536
   185
  }     
jacint@536
   186
  noerror=noerror && coincide;
jacint@536
   187
jacint@536
   188
jacint@536
   189
  std::cout<<"Checking if there is no edge between D and C...";
jacint@536
   190
  bool noedge=true;
jacint@536
   191
  EdgeIt e;
jacint@536
   192
  for(G.first(e); G.valid(e); G.next(e) ) {
jacint@536
   193
    if ( (pos[G.head(e)]==max_matching.C && pos[G.tail(e)]==max_matching.D) || 
jacint@536
   194
	 (pos[G.head(e)]==max_matching.D && pos[G.tail(e)]==max_matching.C) )
jacint@536
   195
      noedge=false; 
jacint@536
   196
  }
jacint@536
   197
  if ( noedge ) std::cout<<"OK"<<std::endl;
jacint@536
   198
  else std::cout<< "There are edges between D and C!"<< std::endl;
jacint@536
   199
  noerror = noerror && noedge;
jacint@536
   200
jacint@536
   201
jacint@536
   202
  std::cout<<"Checking if all the components of G[D] are odd...";
jacint@536
   203
  bool oddcomp=true;
jacint@536
   204
  UGW::NodeMap<bool> todo(G,true);
jacint@536
   205
  int num_comp=0;
jacint@536
   206
  for(G.first(v); G.valid(v); G.next(v) ) {
jacint@536
   207
    if ( pos[v]==max_matching.D && todo[v] ) {
jacint@536
   208
      int comp_size=1;
jacint@536
   209
      ++num_comp;
jacint@536
   210
      std::queue<Node> Q;
jacint@536
   211
      Q.push(v);
jacint@536
   212
      todo.set(v,false);
jacint@536
   213
      while (!Q.empty()) {
jacint@536
   214
	Node w=Q.front();	
jacint@536
   215
	Q.pop();
jacint@536
   216
	OutEdgeIt e;
jacint@536
   217
	for(G.first(e,w); G.valid(e); G.next(e)) {
jacint@536
   218
	  Node u=G.bNode(e);
jacint@536
   219
	  if ( pos[u]==max_matching.D && todo[u] ) {
jacint@536
   220
	    ++comp_size;
jacint@536
   221
	    Q.push(u);
jacint@536
   222
	    todo.set(u,false);
jacint@536
   223
	  }
jacint@536
   224
	}
jacint@536
   225
      }
jacint@536
   226
      if ( !(comp_size % 2) ) oddcomp=false;  
jacint@536
   227
    }
jacint@536
   228
  }
jacint@536
   229
  std::cout << "\n  found     " << num_comp << "     component(s) of G[D],";
jacint@536
   230
  if ( oddcomp ) std::cout<<" each is odd."<<std::endl;
jacint@536
   231
  else std::cout<< " but not all are odd!"<< std::endl;
jacint@536
   232
  noerror = noerror && oddcomp;
jacint@536
   233
jacint@536
   234
jacint@536
   235
  int barrier=0;
jacint@536
   236
  for(G.first(v); G.valid(v); G.next(v) ) 
jacint@536
   237
    if ( pos[v]==max_matching.A ) ++barrier;
jacint@536
   238
  std::cout << barrier << " is the number of nodes in A (i.e. the size of the barrier), so" << std::endl;
jacint@536
   239
  std::cout << num_comp - barrier << " is the deficiency of the graph, and hence" << std::endl; 
jacint@536
   240
  int expected_size=(int)(G.nodeNum()-num_comp+barrier)/2;
jacint@536
   241
  std::cout << expected_size << " should be the size of the maximum matching," << std::endl; 
jacint@536
   242
  if ( size==expected_size )
jacint@536
   243
    std::cout<<"which equals to the number of vertices missed by the found matching!"<<std::endl; 
jacint@536
   244
  else {
jacint@536
   245
    std::cout<<"which does not equal to the number of vertices missed by the matchings found!"
jacint@536
   246
	     <<std::endl; 
jacint@536
   247
    noerror=false;
jacint@536
   248
  }
jacint@536
   249
jacint@536
   250
jacint@536
   251
  if ( num_comp == 1 && barrier == 0 ) 
jacint@536
   252
    std::cout<<"\nThis graph is factor-critical."<<std::endl;
jacint@536
   253
  if ( num_comp == 0 && barrier == 0 ) 
jacint@536
   254
    std::cout<<"\nThis graph has a perfect matching."<<std::endl;
jacint@536
   255
jacint@536
   256
jacint@536
   257
  if( noerror ) std::cout<<"\nNo errors found.\n"<<std::endl;
jacint@536
   258
  else std::cout<<"\nSome errors found!\n"<<std::endl;
jacint@536
   259
jacint@536
   260
  return 0;
jacint@536
   261
}
jacint@536
   262
jacint@536
   263
jacint@536
   264
jacint@536
   265
jacint@536
   266
jacint@536
   267
jacint@536
   268
jacint@536
   269
jacint@536
   270