lemon-0.x: src/work/jacint/max_matching.cc@0274efa2222f

     1 ///Generates a random graph, and tests max_matching.h on it.

     2 #include <iostream>

     3 #include <queue>

     4 #include <math.h>

     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>

    13 using namespace lemon;

    15 int main(int, char **) {

    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;

    24   UGW G;

    26   //  random_init(); //If you want to use a random graph with a random

    27   //  number of edges and nodes.

    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;

    36   //  readDimacs(std::cin, G);

    37   randomGraph(G, i, j );

    39   Timer ts;

    40   bool noerror=true;

    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);

    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   }

    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;

    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;

    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);

   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);

   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);

   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;

   170   std::cout<<"\nChecking the dual..."<<std::endl;

   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;

   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;

   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;

   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   }

   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;

   257   if( noerror ) std::cout<<"\nNo errors found.\n"<<std::endl;

   258   else std::cout<<"\nSome errors found!\n"<<std::endl;

   260   return 0;

   261 }

author	ladanyi
	Tue, 05 Apr 2005 22:37:19 +0000
changeset 1308	0274efa2222f
parent 921	818510fa3d99
permissions	-rw-r--r--