benchmark/swap_bipartite_bench.cc
author alpar
Wed, 08 Nov 2006 23:40:08 +0000
changeset 2295 e464aaa8cdd7
parent 2239 18c24fe93b99
child 2386 81b47fc5c444
permissions -rw-r--r--
Send message to the commit author, as well
deba@2084
     1
#include <cstdlib>
deba@2084
     2
#include <iostream>
deba@2084
     3
#include <sstream>
deba@2084
     4
deba@2084
     5
#include <lemon/smart_graph.h>
alpar@2239
     6
#include <lemon/list_graph.h>
deba@2084
     7
deba@2084
     8
#include <lemon/bpugraph_adaptor.h>
deba@2084
     9
#include <lemon/bipartite_matching.h>
deba@2084
    10
deba@2084
    11
#include <lemon/graph_utils.h>
deba@2084
    12
#include <lemon/graph_to_eps.h>
deba@2084
    13
deba@2084
    14
#include <lemon/time_measure.h>
deba@2242
    15
#include <lemon/random.h>
deba@2084
    16
deba@2084
    17
using namespace std;
deba@2084
    18
using namespace lemon;
deba@2084
    19
deba@2084
    20
typedef SmartBpUGraph Graph;
alpar@2239
    21
typedef ListBpUGraph LGraph;
deba@2084
    22
BPUGRAPH_TYPEDEFS(Graph);
deba@2084
    23
deba@2084
    24
deba@2084
    25
int main() {
deba@2084
    26
deba@2084
    27
  for (int k = 1; k < 100; ++k) {
deba@2084
    28
    
deba@2084
    29
    int n = k * 100;
deba@2084
    30
    int m = (100 - k) * 100;
deba@2084
    31
    int e = 20000;
deba@2084
    32
    int s = 100;
deba@2084
    33
    
deba@2084
    34
    Timer nt(false), st(false);
alpar@2239
    35
    Timer lnt(false), lst(false);
deba@2084
    36
    
deba@2084
    37
    for (int i = 0; i < s; ++i) {
deba@2084
    38
      Graph graph;
alpar@2239
    39
      LGraph lgraph;
deba@2084
    40
      vector<Node> aNodes;
deba@2084
    41
      vector<Node> bNodes;  
alpar@2239
    42
      vector<LGraph::Node> laNodes;
alpar@2239
    43
      vector<LGraph::Node> lbNodes;  
deba@2084
    44
      
deba@2084
    45
      for (int i = 0; i < n; ++i) {
deba@2084
    46
        Node node = graph.addANode();
deba@2084
    47
        aNodes.push_back(node);
alpar@2239
    48
        LGraph::Node lnode = lgraph.addANode();
alpar@2239
    49
        laNodes.push_back(lnode);
deba@2084
    50
      }
deba@2084
    51
      for (int i = 0; i < m; ++i) {
deba@2084
    52
        Node node = graph.addBNode();
deba@2084
    53
        bNodes.push_back(node);
alpar@2239
    54
        LGraph::Node lnode = lgraph.addBNode();
alpar@2239
    55
        lbNodes.push_back(lnode);
deba@2084
    56
      }
deba@2084
    57
      for (int i = 0; i < e; ++i) {
alpar@2239
    58
        int a,b;
deba@2242
    59
	Node aNode = aNodes[a=rnd[n]];
deba@2242
    60
        Node bNode = bNodes[b=rnd[m]];
deba@2084
    61
        graph.addEdge(aNode, bNode);
alpar@2239
    62
	LGraph::Node laNode = laNodes[a];
alpar@2239
    63
        LGraph::Node lbNode = lbNodes[b];
alpar@2239
    64
        lgraph.addEdge(laNode, lbNode);
deba@2084
    65
      }
deba@2084
    66
deba@2084
    67
      {
deba@2084
    68
        MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2084
    69
        
deba@2084
    70
        nt.start();
deba@2084
    71
        bpmatch.init();
deba@2084
    72
        bpmatch.start();
deba@2084
    73
        nt.stop();
deba@2084
    74
        
deba@2084
    75
      }
deba@2084
    76
deba@2084
    77
      {
deba@2084
    78
        typedef SwapBpUGraphAdaptor<Graph> SGraph;
deba@2084
    79
        SGraph sgraph(graph);
deba@2084
    80
        MaxBipartiteMatching<SGraph> bpmatch(sgraph);
deba@2084
    81
deba@2084
    82
        st.start();
deba@2084
    83
        bpmatch.init();
deba@2084
    84
        bpmatch.start();
deba@2084
    85
        st.stop();
deba@2084
    86
        
alpar@2239
    87
      }                 
alpar@2239
    88
      {
alpar@2239
    89
        MaxBipartiteMatching<LGraph> bpmatch(lgraph);
alpar@2239
    90
        
alpar@2239
    91
        lnt.start();
alpar@2239
    92
        bpmatch.init();
alpar@2239
    93
        bpmatch.start();
alpar@2239
    94
        lnt.stop();
alpar@2239
    95
        
deba@2084
    96
      }
deba@2084
    97
alpar@2239
    98
      {
alpar@2239
    99
        typedef SwapBpUGraphAdaptor<LGraph> SGraph;
alpar@2239
   100
        SGraph sgraph(lgraph);
alpar@2239
   101
        MaxBipartiteMatching<SGraph> bpmatch(sgraph);
alpar@2239
   102
alpar@2239
   103
        lst.start();
alpar@2239
   104
        bpmatch.init();
alpar@2239
   105
        bpmatch.start();
alpar@2239
   106
        lst.stop();
alpar@2239
   107
        
alpar@2239
   108
      }
alpar@2239
   109
     }
alpar@2239
   110
alpar@2239
   111
    cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()
alpar@2239
   112
	 << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;
deba@2084
   113
deba@2084
   114
  }
deba@2084
   115
deba@2084
   116
  return 0;
deba@2084
   117
}