benchmark/swap_bipartite_bench.cc
author deba
Tue, 28 Aug 2007 14:00:42 +0000
changeset 2467 2025a571895e
parent 2386 81b47fc5c444
child 2553 bfced05fa852
permissions -rw-r--r--
PathNodeIt

PathWriter/Reader structures
Distinict MapSet readers and writers
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #include <cstdlib>
    20 #include <iostream>
    21 #include <sstream>
    22 
    23 #include <lemon/smart_graph.h>
    24 #include <lemon/list_graph.h>
    25 
    26 #include <lemon/bpugraph_adaptor.h>
    27 #include <lemon/bipartite_matching.h>
    28 
    29 #include <lemon/graph_utils.h>
    30 #include <lemon/graph_to_eps.h>
    31 
    32 #include <lemon/time_measure.h>
    33 #include <lemon/random.h>
    34 
    35 using namespace std;
    36 using namespace lemon;
    37 
    38 typedef SmartBpUGraph Graph;
    39 typedef ListBpUGraph LGraph;
    40 BPUGRAPH_TYPEDEFS(Graph);
    41 
    42 
    43 int main() {
    44 
    45   for (int k = 1; k < 100; ++k) {
    46     
    47     int n = k * 100;
    48     int m = (100 - k) * 100;
    49     int e = 20000;
    50     int s = 100;
    51     
    52     Timer nt(false), st(false);
    53     Timer lnt(false), lst(false);
    54     
    55     for (int i = 0; i < s; ++i) {
    56       Graph graph;
    57       LGraph lgraph;
    58       vector<Node> aNodes;
    59       vector<Node> bNodes;  
    60       vector<LGraph::Node> laNodes;
    61       vector<LGraph::Node> lbNodes;  
    62       
    63       for (int j = 0; j < n; ++j) {
    64         Node node = graph.addANode();
    65         aNodes.push_back(node);
    66         LGraph::Node lnode = lgraph.addANode();
    67         laNodes.push_back(lnode);
    68       }
    69       for (int j = 0; j < m; ++j) {
    70         Node node = graph.addBNode();
    71         bNodes.push_back(node);
    72         LGraph::Node lnode = lgraph.addBNode();
    73         lbNodes.push_back(lnode);
    74       }
    75       for (int j = 0; j < e; ++j) {
    76         int a,b;
    77 	Node aNode = aNodes[a=rnd[n]];
    78         Node bNode = bNodes[b=rnd[m]];
    79         graph.addEdge(aNode, bNode);
    80 	LGraph::Node laNode = laNodes[a];
    81         LGraph::Node lbNode = lbNodes[b];
    82         lgraph.addEdge(laNode, lbNode);
    83       }
    84 
    85       {
    86         MaxBipartiteMatching<Graph> bpmatch(graph);
    87         
    88         nt.start();
    89         bpmatch.init();
    90         bpmatch.start();
    91         nt.stop();
    92         
    93       }
    94 
    95       {
    96         typedef SwapBpUGraphAdaptor<Graph> SGraph;
    97         SGraph sgraph(graph);
    98         MaxBipartiteMatching<SGraph> bpmatch(sgraph);
    99 
   100         st.start();
   101         bpmatch.init();
   102         bpmatch.start();
   103         st.stop();
   104         
   105       }                 
   106       {
   107         MaxBipartiteMatching<LGraph> bpmatch(lgraph);
   108         
   109         lnt.start();
   110         bpmatch.init();
   111         bpmatch.start();
   112         lnt.stop();
   113         
   114       }
   115 
   116       {
   117         typedef SwapBpUGraphAdaptor<LGraph> SGraph;
   118         SGraph sgraph(lgraph);
   119         MaxBipartiteMatching<SGraph> bpmatch(sgraph);
   120 
   121         lst.start();
   122         bpmatch.init();
   123         bpmatch.start();
   124         lst.stop();
   125         
   126       }
   127      }
   128 
   129     cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()
   130 	 << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;
   131 
   132   }
   133 
   134   return 0;
   135 }