benchmark/swap_bipartite_bench.cc
author deba
Mon, 14 Aug 2006 16:08:28 +0000
changeset 2180 d5544c9409e4
parent 2084 59769591eb60
child 2207 75a29ac69c19
permissions -rw-r--r--
Omit warning
Using check instead of the LEMON_ASSERT
Using fixed graph
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>
deba@2084
     6
deba@2084
     7
#include <lemon/bpugraph_adaptor.h>
deba@2084
     8
#include <lemon/bipartite_matching.h>
deba@2084
     9
deba@2084
    10
#include <lemon/graph_utils.h>
deba@2084
    11
#include <lemon/xy.h>
deba@2084
    12
#include <lemon/graph_to_eps.h>
deba@2084
    13
deba@2084
    14
#include <lemon/time_measure.h>
deba@2084
    15
deba@2084
    16
using namespace std;
deba@2084
    17
using namespace lemon;
deba@2084
    18
deba@2084
    19
typedef SmartBpUGraph Graph;
deba@2084
    20
BPUGRAPH_TYPEDEFS(Graph);
deba@2084
    21
deba@2084
    22
int _urandom_init() {
deba@2084
    23
  int seed = time(0);
deba@2084
    24
  srand(seed);
deba@2084
    25
  return seed;
deba@2084
    26
}
deba@2084
    27
deba@2084
    28
int urandom(int n) {
deba@2084
    29
  static int seed = _urandom_init();
deba@2130
    30
  ignore_unused_variable_warning(seed);
deba@2084
    31
  return (int)(rand() / (1.0 + RAND_MAX) * n);
deba@2084
    32
}
deba@2084
    33
deba@2084
    34
int main() {
deba@2084
    35
deba@2084
    36
  for (int k = 1; k < 100; ++k) {
deba@2084
    37
    
deba@2084
    38
    int n = k * 100;
deba@2084
    39
    int m = (100 - k) * 100;
deba@2084
    40
    int e = 20000;
deba@2084
    41
    int s = 100;
deba@2084
    42
    
deba@2084
    43
    Timer nt(false), st(false);
deba@2084
    44
    
deba@2084
    45
    for (int i = 0; i < s; ++i) {
deba@2084
    46
      Graph graph;
deba@2084
    47
      vector<Node> aNodes;
deba@2084
    48
      vector<Node> bNodes;  
deba@2084
    49
      
deba@2084
    50
      for (int i = 0; i < n; ++i) {
deba@2084
    51
        Node node = graph.addANode();
deba@2084
    52
        aNodes.push_back(node);
deba@2084
    53
      }
deba@2084
    54
      for (int i = 0; i < m; ++i) {
deba@2084
    55
        Node node = graph.addBNode();
deba@2084
    56
        bNodes.push_back(node);
deba@2084
    57
      }
deba@2084
    58
      for (int i = 0; i < e; ++i) {
deba@2084
    59
        Node aNode = aNodes[urandom(n)];
deba@2084
    60
        Node bNode = bNodes[urandom(m)];
deba@2084
    61
        graph.addEdge(aNode, bNode);
deba@2084
    62
      }
deba@2084
    63
deba@2084
    64
      {
deba@2084
    65
        MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2084
    66
        
deba@2084
    67
        nt.start();
deba@2084
    68
        bpmatch.init();
deba@2084
    69
        bpmatch.start();
deba@2084
    70
        nt.stop();
deba@2084
    71
        
deba@2084
    72
      }
deba@2084
    73
deba@2084
    74
      {
deba@2084
    75
        typedef SwapBpUGraphAdaptor<Graph> SGraph;
deba@2084
    76
        SGraph sgraph(graph);
deba@2084
    77
        MaxBipartiteMatching<SGraph> bpmatch(sgraph);
deba@2084
    78
deba@2084
    79
        st.start();
deba@2084
    80
        bpmatch.init();
deba@2084
    81
        bpmatch.start();
deba@2084
    82
        st.stop();
deba@2084
    83
        
deba@2084
    84
      }
deba@2084
    85
                  
deba@2084
    86
    }
deba@2084
    87
deba@2084
    88
    cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
deba@2084
    89
deba@2084
    90
  }
deba@2084
    91
deba@2084
    92
  return 0;
deba@2084
    93
}