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

}