/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2007

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #include <cstdlib>

 #include <iostream>

 #include <sstream>

 #include <lemon/smart_graph.h>

 #include <lemon/list_graph.h>

 #include <lemon/bpugraph_adaptor.h>

 #include <lemon/bipartite_matching.h>

 #include <lemon/graph_utils.h>

 #include <lemon/graph_to_eps.h>

 #include <lemon/time_measure.h>

 #include <lemon/random.h>

 using namespace std;

 using namespace lemon;

 typedef SmartBpUGraph Graph;

 typedef ListBpUGraph LGraph;

 BPUGRAPH_TYPEDEFS(Graph);

 int main() {

   for (int k = 1; k < 100; ++k) {

     int n = k * 100;

     int m = (100 - k) * 100;

     int e = 20000;

     int s = 100;

     Timer nt(false), st(false);

     Timer lnt(false), lst(false);

     for (int i = 0; i < s; ++i) {

       Graph graph;

       LGraph lgraph;

       vector<Node> aNodes;

       vector<Node> bNodes;  

       vector<LGraph::Node> laNodes;

       vector<LGraph::Node> lbNodes;  

       for (int j = 0; j < n; ++j) {

         Node node = graph.addANode();

         aNodes.push_back(node);

         LGraph::Node lnode = lgraph.addANode();

         laNodes.push_back(lnode);

       }

       for (int j = 0; j < m; ++j) {

         Node node = graph.addBNode();

         bNodes.push_back(node);

         LGraph::Node lnode = lgraph.addBNode();

         lbNodes.push_back(lnode);

       }

       for (int j = 0; j < e; ++j) {

         int a,b;

 	Node aNode = aNodes[a=rnd[n]];

         Node bNode = bNodes[b=rnd[m]];

         graph.addEdge(aNode, bNode);

 	LGraph::Node laNode = laNodes[a];

         LGraph::Node lbNode = lbNodes[b];

         lgraph.addEdge(laNode, lbNode);

       }

       {

         MaxBipartiteMatching<Graph> bpmatch(graph);

         nt.start();

         bpmatch.init();

         bpmatch.start();

         nt.stop();

       }

       {

         typedef SwapBpUGraphAdaptor<Graph> SGraph;

         SGraph sgraph(graph);

         MaxBipartiteMatching<SGraph> bpmatch(sgraph);

         st.start();

         bpmatch.init();

         bpmatch.start();

         st.stop();

       }                 

       {

         MaxBipartiteMatching<LGraph> bpmatch(lgraph);

         lnt.start();

         bpmatch.init();

         bpmatch.start();

         lnt.stop();

       }

       {

         typedef SwapBpUGraphAdaptor<LGraph> SGraph;

         SGraph sgraph(lgraph);

         MaxBipartiteMatching<SGraph> bpmatch(sgraph);

         lst.start();

         bpmatch.init();

         bpmatch.start();

         lst.stop();

       }

      }

     cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()

 	 << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;

   }

   return 0;

 }