// -*- 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;
}