/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2008

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

}