// -*- c++ -*-

 #include <iostream>

 #include <fstream>

 #include <vector>

 #include <cstdlib>

 #include <LEDA/graph.h>

 #include <LEDA/mc_matching.h>

 #include <LEDA/list.h>

 #include <LEDA/graph_gen.h>

 #include <leda_graph_wrapper.h>

 #include <list_graph.h>

 #include <dimacs.h>

 #include <time_measure.h>

 #include <for_each_macros.h>

 #include <graph_wrapper.h>

 #include <bipartite_graph_wrapper.h>

 #include <maps.h>

 #include <max_matching.h>

 // /**

 //  * Inicializalja a veletlenszamgeneratort.

 //  * Figyelem, ez nem jo igazi random szamokhoz,

 //  * erre ne bizzad a titkaidat!

 //  */

 // void random_init()

 // {

 // 	unsigned int seed = getpid();

 // 	seed |= seed << 15;

 // 	seed ^= time(0);

 // 	srand(seed);

 // }

 // /**

 //  * Egy veletlen int-et ad vissza 0 es m-1 kozott.

 //  */

 // int random(int m)

 // {

 //   return int( double(m) * rand() / (RAND_MAX + 1.0) );

 // }

 using namespace lemon;

 int main() {

   //for leda graph

   leda::graph lg;

   //lg.make_undirected();

   typedef LedaGraphWrapper<leda::graph> Graph;

   Graph g(lg);

   //for UndirListGraph

   //typedef UndirListGraph Graph; 

   //Graph g;

   typedef Graph::Node Node;

   typedef Graph::NodeIt NodeIt;

   typedef Graph::Edge Edge;

   typedef Graph::EdgeIt EdgeIt;

   typedef Graph::OutEdgeIt OutEdgeIt;

   std::vector<Graph::Node> s_nodes;

   std::vector<Graph::Node> t_nodes;

   int n;

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

   std::cin >> n; 

   int m;

   std::cout << "number of edges=";

   std::cin >> m; 

   std::cout << std::endl;

   random_graph(lg, n, m);

   Timer ts;

   //  writeDimacs(std::cout, g); //for check

   MaxMatching<Graph> max_matching(g);

   std::cout << 

     "Running the edmonds algorithm run()... " 

 	    <<std::endl;

   ts.reset();  

   max_matching.run();

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

   int s=0;

   Graph::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 run(),"<<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;

   }

   ts.reset();  

   leda_list<leda_edge> ml=MAX_CARD_MATCHING(lg);

   std::cout << "LEDA max matching algorithm." << std::endl 

 	    << "Size of matching: " 

 	    << ml.size() << std::endl;

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

   std::cout << "\n";

   return 0;

 }