benchmark/swap_bipartite_bench.cc
author deba
Tue, 30 May 2006 10:33:50 +0000
changeset 2098 12f67fa3df7d
child 2130 244e108de26f
permissions -rw-r--r--
Bug fix in the list bipartite undirected 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@2084
    30
  return (int)(rand() / (1.0 + RAND_MAX) * n);
deba@2084
    31
}
deba@2084
    32
deba@2084
    33
int main() {
deba@2084
    34
deba@2084
    35
  for (int k = 1; k < 100; ++k) {
deba@2084
    36
    
deba@2084
    37
    int n = k * 100;
deba@2084
    38
    int m = (100 - k) * 100;
deba@2084
    39
    int e = 20000;
deba@2084
    40
    int s = 100;
deba@2084
    41
    
deba@2084
    42
    Timer nt(false), st(false);
deba@2084
    43
    
deba@2084
    44
    for (int i = 0; i < s; ++i) {
deba@2084
    45
      Graph graph;
deba@2084
    46
      vector<Node> aNodes;
deba@2084
    47
      vector<Node> bNodes;  
deba@2084
    48
      
deba@2084
    49
      for (int i = 0; i < n; ++i) {
deba@2084
    50
        Node node = graph.addANode();
deba@2084
    51
        aNodes.push_back(node);
deba@2084
    52
      }
deba@2084
    53
      for (int i = 0; i < m; ++i) {
deba@2084
    54
        Node node = graph.addBNode();
deba@2084
    55
        bNodes.push_back(node);
deba@2084
    56
      }
deba@2084
    57
      for (int i = 0; i < e; ++i) {
deba@2084
    58
        Node aNode = aNodes[urandom(n)];
deba@2084
    59
        Node bNode = bNodes[urandom(m)];
deba@2084
    60
        graph.addEdge(aNode, bNode);
deba@2084
    61
      }
deba@2084
    62
deba@2084
    63
      {
deba@2084
    64
        MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2084
    65
        
deba@2084
    66
        nt.start();
deba@2084
    67
        bpmatch.init();
deba@2084
    68
        bpmatch.start();
deba@2084
    69
        nt.stop();
deba@2084
    70
        
deba@2084
    71
      }
deba@2084
    72
deba@2084
    73
      {
deba@2084
    74
        typedef SwapBpUGraphAdaptor<Graph> SGraph;
deba@2084
    75
        SGraph sgraph(graph);
deba@2084
    76
        MaxBipartiteMatching<SGraph> bpmatch(sgraph);
deba@2084
    77
deba@2084
    78
        st.start();
deba@2084
    79
        bpmatch.init();
deba@2084
    80
        bpmatch.start();
deba@2084
    81
        st.stop();
deba@2084
    82
        
deba@2084
    83
      }
deba@2084
    84
                  
deba@2084
    85
    }
deba@2084
    86
deba@2084
    87
    cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
deba@2084
    88
deba@2084
    89
  }
deba@2084
    90
deba@2084
    91
  return 0;
deba@2084
    92
}