alpar@2391: /* -*- C++ -*-
alpar@2391:  *
alpar@2391:  * This file is a part of LEMON, a generic C++ optimization library
alpar@2391:  *
alpar@2391:  * Copyright (C) 2003-2007
alpar@2391:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
alpar@2391:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
alpar@2391:  *
alpar@2391:  * Permission to use, modify and distribute this software is granted
alpar@2391:  * provided that this copyright notice appears in all copies. For
alpar@2391:  * precise terms see the accompanying LICENSE file.
alpar@2391:  *
alpar@2391:  * This software is provided "AS IS" with no warranty of any kind,
alpar@2391:  * express or implied, and with no claim as to its suitability for any
alpar@2391:  * purpose.
alpar@2391:  *
alpar@2391:  */
alpar@2391: 
deba@2084: #include <cstdlib>
deba@2084: #include <iostream>
deba@2084: #include <sstream>
deba@2084: 
deba@2084: #include <lemon/smart_graph.h>
alpar@2239: #include <lemon/list_graph.h>
deba@2084: 
deba@2084: #include <lemon/bpugraph_adaptor.h>
deba@2084: #include <lemon/bipartite_matching.h>
deba@2084: 
deba@2084: #include <lemon/graph_utils.h>
deba@2084: #include <lemon/graph_to_eps.h>
deba@2084: 
deba@2084: #include <lemon/time_measure.h>
deba@2242: #include <lemon/random.h>
deba@2084: 
deba@2084: using namespace std;
deba@2084: using namespace lemon;
deba@2084: 
deba@2084: typedef SmartBpUGraph Graph;
alpar@2239: typedef ListBpUGraph LGraph;
deba@2084: BPUGRAPH_TYPEDEFS(Graph);
deba@2084: 
deba@2084: 
deba@2084: int main() {
deba@2084: 
deba@2084:   for (int k = 1; k < 100; ++k) {
deba@2084:     
deba@2084:     int n = k * 100;
deba@2084:     int m = (100 - k) * 100;
deba@2084:     int e = 20000;
deba@2084:     int s = 100;
deba@2084:     
deba@2084:     Timer nt(false), st(false);
alpar@2239:     Timer lnt(false), lst(false);
deba@2084:     
deba@2084:     for (int i = 0; i < s; ++i) {
deba@2084:       Graph graph;
alpar@2239:       LGraph lgraph;
deba@2084:       vector<Node> aNodes;
deba@2084:       vector<Node> bNodes;  
alpar@2239:       vector<LGraph::Node> laNodes;
alpar@2239:       vector<LGraph::Node> lbNodes;  
deba@2084:       
deba@2386:       for (int j = 0; j < n; ++j) {
deba@2084:         Node node = graph.addANode();
deba@2084:         aNodes.push_back(node);
alpar@2239:         LGraph::Node lnode = lgraph.addANode();
alpar@2239:         laNodes.push_back(lnode);
deba@2084:       }
deba@2386:       for (int j = 0; j < m; ++j) {
deba@2084:         Node node = graph.addBNode();
deba@2084:         bNodes.push_back(node);
alpar@2239:         LGraph::Node lnode = lgraph.addBNode();
alpar@2239:         lbNodes.push_back(lnode);
deba@2084:       }
deba@2386:       for (int j = 0; j < e; ++j) {
alpar@2239:         int a,b;
deba@2242: 	Node aNode = aNodes[a=rnd[n]];
deba@2242:         Node bNode = bNodes[b=rnd[m]];
deba@2084:         graph.addEdge(aNode, bNode);
alpar@2239: 	LGraph::Node laNode = laNodes[a];
alpar@2239:         LGraph::Node lbNode = lbNodes[b];
alpar@2239:         lgraph.addEdge(laNode, lbNode);
deba@2084:       }
deba@2084: 
deba@2084:       {
deba@2084:         MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2084:         
deba@2084:         nt.start();
deba@2084:         bpmatch.init();
deba@2084:         bpmatch.start();
deba@2084:         nt.stop();
deba@2084:         
deba@2084:       }
deba@2084: 
deba@2084:       {
deba@2084:         typedef SwapBpUGraphAdaptor<Graph> SGraph;
deba@2084:         SGraph sgraph(graph);
deba@2084:         MaxBipartiteMatching<SGraph> bpmatch(sgraph);
deba@2084: 
deba@2084:         st.start();
deba@2084:         bpmatch.init();
deba@2084:         bpmatch.start();
deba@2084:         st.stop();
deba@2084:         
alpar@2239:       }                 
alpar@2239:       {
alpar@2239:         MaxBipartiteMatching<LGraph> bpmatch(lgraph);
alpar@2239:         
alpar@2239:         lnt.start();
alpar@2239:         bpmatch.init();
alpar@2239:         bpmatch.start();
alpar@2239:         lnt.stop();
alpar@2239:         
deba@2084:       }
deba@2084: 
alpar@2239:       {
alpar@2239:         typedef SwapBpUGraphAdaptor<LGraph> SGraph;
alpar@2239:         SGraph sgraph(lgraph);
alpar@2239:         MaxBipartiteMatching<SGraph> bpmatch(sgraph);
alpar@2239: 
alpar@2239:         lst.start();
alpar@2239:         bpmatch.init();
alpar@2239:         bpmatch.start();
alpar@2239:         lst.stop();
alpar@2239:         
alpar@2239:       }
alpar@2239:      }
alpar@2239: 
alpar@2239:     cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()
alpar@2239: 	 << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;
deba@2084: 
deba@2084:   }
deba@2084: 
deba@2084:   return 0;
deba@2084: }