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