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