benchmark/swap_bipartite_bench.cc
changeset 2092 fc18c2b50a8f
child 2130 244e108de26f
equal deleted inserted replaced
-1:000000000000 0:819a2ec6f70b
       
     1 #include <cstdlib>
       
     2 #include <iostream>
       
     3 #include <sstream>
       
     4 
       
     5 #include <lemon/smart_graph.h>
       
     6 
       
     7 #include <lemon/bpugraph_adaptor.h>
       
     8 #include <lemon/bipartite_matching.h>
       
     9 
       
    10 #include <lemon/graph_utils.h>
       
    11 #include <lemon/xy.h>
       
    12 #include <lemon/graph_to_eps.h>
       
    13 
       
    14 #include <lemon/time_measure.h>
       
    15 
       
    16 using namespace std;
       
    17 using namespace lemon;
       
    18 
       
    19 typedef SmartBpUGraph Graph;
       
    20 BPUGRAPH_TYPEDEFS(Graph);
       
    21 
       
    22 int _urandom_init() {
       
    23   int seed = time(0);
       
    24   srand(seed);
       
    25   return seed;
       
    26 }
       
    27 
       
    28 int urandom(int n) {
       
    29   static int seed = _urandom_init();
       
    30   return (int)(rand() / (1.0 + RAND_MAX) * n);
       
    31 }
       
    32 
       
    33 int main() {
       
    34 
       
    35   for (int k = 1; k < 100; ++k) {
       
    36     
       
    37     int n = k * 100;
       
    38     int m = (100 - k) * 100;
       
    39     int e = 20000;
       
    40     int s = 100;
       
    41     
       
    42     Timer nt(false), st(false);
       
    43     
       
    44     for (int i = 0; i < s; ++i) {
       
    45       Graph graph;
       
    46       vector<Node> aNodes;
       
    47       vector<Node> bNodes;  
       
    48       
       
    49       for (int i = 0; i < n; ++i) {
       
    50         Node node = graph.addANode();
       
    51         aNodes.push_back(node);
       
    52       }
       
    53       for (int i = 0; i < m; ++i) {
       
    54         Node node = graph.addBNode();
       
    55         bNodes.push_back(node);
       
    56       }
       
    57       for (int i = 0; i < e; ++i) {
       
    58         Node aNode = aNodes[urandom(n)];
       
    59         Node bNode = bNodes[urandom(m)];
       
    60         graph.addEdge(aNode, bNode);
       
    61       }
       
    62 
       
    63       {
       
    64         MaxBipartiteMatching<Graph> bpmatch(graph);
       
    65         
       
    66         nt.start();
       
    67         bpmatch.init();
       
    68         bpmatch.start();
       
    69         nt.stop();
       
    70         
       
    71       }
       
    72 
       
    73       {
       
    74         typedef SwapBpUGraphAdaptor<Graph> SGraph;
       
    75         SGraph sgraph(graph);
       
    76         MaxBipartiteMatching<SGraph> bpmatch(sgraph);
       
    77 
       
    78         st.start();
       
    79         bpmatch.init();
       
    80         bpmatch.start();
       
    81         st.stop();
       
    82         
       
    83       }
       
    84                   
       
    85     }
       
    86 
       
    87     cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
       
    88 
       
    89   }
       
    90 
       
    91   return 0;
       
    92 }