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

 #include <iostream>

 #include <queue>

 #include <math.h>

 #include <list_graph.h>

 #include <dimacs.h>

 #include <graph_gen.h>

 #include <max_matching.h>

 #include <time_measure.h>

 #include <graph_wrapper.h>

 using namespace lemon;

 int main(int, char **) {

   typedef UndirGraph<ListGraph> UGW;

   typedef UGW::Edge Edge;

   typedef UGW::EdgeIt EdgeIt;

   typedef UGW::OutEdgeIt OutEdgeIt;

   typedef UGW::NodeIt NodeIt;

   typedef UGW::Node Node;

   UGW G;

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

   //  number of edges and nodes.

   int i;

   int j;

   std::cout<<"Number of nodes: ";

   std::cin >> i;

   std::cout<<"Number of edges: ";

   std::cin >> j;

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

   randomGraph(G, i, j );  

   Timer ts;

   bool noerror=true;

   std::cout <<

     "\n  Testing max_matching.h on a random graph with " << 

     G.nodeNum() << " nodes and " << G.edgeNum() << " edges...\n"

 	    << std::endl;

   MaxMatching<UGW> max_matching(G);

   std::cout << 

     "Running the plain edmonds algorithm runEdmonds(0) using no heuristic... " 

 	    <<std::endl;

   ts.reset();  

   max_matching.runEdmonds(0);

   std::cout<<"Elapsed time: "<<ts<<std::endl;

   int s=0;

   UGW::NodeMap<Node> mate(G,INVALID);

   max_matching.writeNMapNode(mate);

   NodeIt v;

   for(G.first(v); G.valid(v); G.next(v) ) {

     if ( G.valid(mate[v]) ) {

       ++s;

     }

   }

   int size=(int)s/2;  //size will be used as the size of a maxmatching

   std::cout << size << " is the size of the matching found by runEdmonds(0),"<<std::endl;

   if ( size == max_matching.size() ) {

     std::cout<< "which equals to the size of the actual matching reported by size().\n"<< std::endl;

   } else {  

     std::cout<< "which does not equal to the size of the actual matching reported by size()!\n"<< std::endl;

     noerror=false;

   }

   std::cout<<"Writing the position by calling writePos...";

   UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos0(G);

   max_matching.writePos(pos0);

   std::cout << "OK" << std::endl;

   std::cout << "Resetting the matching and the position by calling"<< std::endl;

   std::cout<<"resetPos() and resetMatching()...";

   max_matching.resetPos();

   max_matching.resetMatching();

   std::cout <<"OK" << std::endl;

   std::cout << "\nRunning runEdmonds(1) using the 'postpone shrink' heuristic ... " <<std::endl;

   ts.reset();  

   max_matching.runEdmonds(1);

   std::cout<<"Elapsed time: "<<ts<<std::endl;

   s=0;

   max_matching.writeNMapNode(mate);

   for(G.first(v); G.valid(v); G.next(v) ) {

     if ( G.valid(mate[v]) ) {

       ++s;

     }

   }

   std::cout << (int)s/2 << 

     " is the size of the matching found by runEdmonds(1),"<<std::endl;

   if ( (int)s/2 == size ) {

     std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl;

   } else {  

     std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;

     noerror=false;

   } 

   UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos1(G);

   max_matching.writePos(pos1);

   std::cout << "\nStarting run() from the matching given by runEdmonds(1)... " <<std::endl;

   max_matching.resetPos();

   ts.reset();  

   max_matching.run();

   std::cout<<"Elapsed time: "<<ts<<std::endl;

   s=0;

   max_matching.writeNMapNode(mate);

   for(G.first(v); G.valid(v); G.next(v) ) {

     if ( G.valid(mate[v]) ) {

       ++s;

     }

   }

   if ( (int)s/2 == size ) {

     std::cout<< "Found a matching of proper size."<< std::endl;

   } else {  

     std::cout<< "Found a matching of inproper size!"<< std::endl;

     noerror=false;

   }

   UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos2(G);

   max_matching.writePos(pos2);

   std::cout << "\nCalling resetPos() and resetMatching()...";

   max_matching.resetPos();

   max_matching.resetMatching();

   std::cout<<"OK"<<std::endl;

   std::cout <<"Calling greedyMatching() and then runEdmonds(1)... " <<std::endl;

   ts.reset();  

   max_matching.run();

   std::cout<<"Elapsed time: "<<ts<<std::endl;

   s=0;

   max_matching.writeNMapNode(mate);

   for(G.first(v); G.valid(v); G.next(v) ) {

     if ( G.valid(mate[v]) ) {

       ++s;

     }

   }

   std::cout << (int)s/2 << " is the size of the matching found by run(),"<<std::endl;

   if ( (int)s/2 == size ) {

     std::cout<< "which equals to the size of the matching found by runEdmonds(0)."<< std::endl;

   } else {  

     std::cout<< "which does not equal to the size of the matching found by runEdmonds(0)!"<< std::endl;

     noerror=false;

   }

   UGW::NodeMap<MaxMatching<UGW>::pos_enum> pos(G);

   max_matching.writePos(pos);

   std::cout<<"\nChecking if the output is a matching...";

   bool ismatching=true;

   for(G.first(v); G.valid(v); G.next(v) )

     if ( G.valid(mate[v]) ) {

       Node u=mate[v];

       if (mate[u]!=v) ismatching=false; 

     }

   if ( ismatching ) std::cout<<"OK"<<std::endl;

   else std::cout<< "It is not a matching!"<< std::endl;

   noerror = noerror && ismatching;

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

   std::cout<<"Checking if the four position outputs coincide...";

   bool coincide=true;

   int err_node=0;

   for(G.first(v); G.valid(v); G.next(v) ) {

     if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {

       ++err_node;

       coincide=false;

     }

   }

   if ( coincide ) std::cout << "OK" <<std::endl;

   else {

     std::cout << "They do not coincide! Number of erroneous nodes: " 

 	      << err_node << std::endl;

   }     

   noerror=noerror && coincide;

   std::cout<<"Checking if there is no edge between D and C...";

   bool noedge=true;

   EdgeIt e;

   for(G.first(e); G.valid(e); G.next(e) ) {

     if ( (pos[G.head(e)]==max_matching.C && pos[G.tail(e)]==max_matching.D) || 

 	 (pos[G.head(e)]==max_matching.D && pos[G.tail(e)]==max_matching.C) )

       noedge=false; 

   }

   if ( noedge ) std::cout<<"OK"<<std::endl;

   else std::cout<< "There are edges between D and C!"<< std::endl;

   noerror = noerror && noedge;

   std::cout<<"Checking if all the components of G[D] are odd...";

   bool oddcomp=true;

   UGW::NodeMap<bool> todo(G,true);

   int num_comp=0;

   for(G.first(v); G.valid(v); G.next(v) ) {

     if ( pos[v]==max_matching.D && todo[v] ) {

       int comp_size=1;

       ++num_comp;

       std::queue<Node> Q;

       Q.push(v);

       todo.set(v,false);

       while (!Q.empty()) {

 	Node w=Q.front();	

 	Q.pop();

 	OutEdgeIt e;

 	for(G.first(e,w); G.valid(e); G.next(e)) {

 	  Node u=G.bNode(e);

 	  if ( pos[u]==max_matching.D && todo[u] ) {

 	    ++comp_size;

 	    Q.push(u);

 	    todo.set(u,false);

 	  }

 	}

       }

       if ( !(comp_size % 2) ) oddcomp=false;  

     }

   }

   std::cout << "\n  found     " << num_comp << "     component(s) of G[D],";

   if ( oddcomp ) std::cout<<" each is odd."<<std::endl;

   else std::cout<< " but not all are odd!"<< std::endl;

   noerror = noerror && oddcomp;

   int barrier=0;

   for(G.first(v); G.valid(v); G.next(v) ) 

     if ( pos[v]==max_matching.A ) ++barrier;

   std::cout << barrier << " is the number of nodes in A (i.e. the size of the barrier), so" << std::endl;

   std::cout << num_comp - barrier << " is the deficiency of the graph, and hence" << std::endl; 

   int expected_size=(int)(G.nodeNum()-num_comp+barrier)/2;

   std::cout << expected_size << " should be the size of the maximum matching," << std::endl; 

   if ( size==expected_size )

     std::cout<<"which equals to the number of vertices missed by the found matching!"<<std::endl; 

   else {

     std::cout<<"which does not equal to the number of vertices missed by the matchings found!"

 	     <<std::endl; 

     noerror=false;

   }

   if ( num_comp == 1 && barrier == 0 ) 

     std::cout<<"\nThis graph is factor-critical."<<std::endl;

   if ( num_comp == 0 && barrier == 0 ) 

     std::cout<<"\nThis graph has a perfect matching."<<std::endl;

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

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

   return 0;

 }