benchmark/swap_bipartite_bench.cc
changeset 2212 0ad3835449f8
parent 2207 75a29ac69c19
child 2232 ae8562537502
equal deleted inserted replaced
2:1dd58b0542eb 3:ee8b27c1772a
     1 #include <cstdlib>
     1 #include <cstdlib>
     2 #include <iostream>
     2 #include <iostream>
     3 #include <sstream>
     3 #include <sstream>
     4 
     4 
     5 #include <lemon/smart_graph.h>
     5 #include <lemon/smart_graph.h>
     6 #include <lemon/list_graph.h>
       
     7 
     6 
     8 #include <lemon/bpugraph_adaptor.h>
     7 #include <lemon/bpugraph_adaptor.h>
     9 #include <lemon/bipartite_matching.h>
     8 #include <lemon/bipartite_matching.h>
    10 
     9 
    11 #include <lemon/graph_utils.h>
    10 #include <lemon/graph_utils.h>
    12 #include <lemon/dim2.h>
    11 #include <lemon/xy.h>
    13 #include <lemon/graph_to_eps.h>
    12 #include <lemon/graph_to_eps.h>
    14 
    13 
    15 #include <lemon/time_measure.h>
    14 #include <lemon/time_measure.h>
    16 
    15 
    17 using namespace std;
    16 using namespace std;
    18 using namespace lemon;
    17 using namespace lemon;
    19 
    18 
    20 typedef SmartBpUGraph Graph;
    19 typedef SmartBpUGraph Graph;
    21 typedef ListBpUGraph LGraph;
       
    22 BPUGRAPH_TYPEDEFS(Graph);
    20 BPUGRAPH_TYPEDEFS(Graph);
    23 
    21 
    24 int _urandom_init() {
    22 int _urandom_init() {
    25   int seed = time(0);
    23   int seed = time(0);
    26   srand(seed);
    24   srand(seed);
    41     int m = (100 - k) * 100;
    39     int m = (100 - k) * 100;
    42     int e = 20000;
    40     int e = 20000;
    43     int s = 100;
    41     int s = 100;
    44     
    42     
    45     Timer nt(false), st(false);
    43     Timer nt(false), st(false);
    46     Timer lnt(false), lst(false);
       
    47     
    44     
    48     for (int i = 0; i < s; ++i) {
    45     for (int i = 0; i < s; ++i) {
    49       Graph graph;
    46       Graph graph;
    50       LGraph lgraph;
       
    51       vector<Node> aNodes;
    47       vector<Node> aNodes;
    52       vector<Node> bNodes;  
    48       vector<Node> bNodes;  
    53       vector<LGraph::Node> laNodes;
       
    54       vector<LGraph::Node> lbNodes;  
       
    55       
    49       
    56       for (int i = 0; i < n; ++i) {
    50       for (int i = 0; i < n; ++i) {
    57         Node node = graph.addANode();
    51         Node node = graph.addANode();
    58         aNodes.push_back(node);
    52         aNodes.push_back(node);
    59         LGraph::Node lnode = lgraph.addANode();
       
    60         laNodes.push_back(lnode);
       
    61       }
    53       }
    62       for (int i = 0; i < m; ++i) {
    54       for (int i = 0; i < m; ++i) {
    63         Node node = graph.addBNode();
    55         Node node = graph.addBNode();
    64         bNodes.push_back(node);
    56         bNodes.push_back(node);
    65         LGraph::Node lnode = lgraph.addBNode();
       
    66         lbNodes.push_back(lnode);
       
    67       }
    57       }
    68       for (int i = 0; i < e; ++i) {
    58       for (int i = 0; i < e; ++i) {
    69         int a,b;
    59         Node aNode = aNodes[urandom(n)];
    70 	Node aNode = aNodes[a=urandom(n)];
    60         Node bNode = bNodes[urandom(m)];
    71         Node bNode = bNodes[b=urandom(m)];
       
    72         graph.addEdge(aNode, bNode);
    61         graph.addEdge(aNode, bNode);
    73 	LGraph::Node laNode = laNodes[a];
       
    74         LGraph::Node lbNode = lbNodes[b];
       
    75         lgraph.addEdge(laNode, lbNode);
       
    76       }
    62       }
    77 
    63 
    78       {
    64       {
    79         MaxBipartiteMatching<Graph> bpmatch(graph);
    65         MaxBipartiteMatching<Graph> bpmatch(graph);
    80         
    66         
    93         st.start();
    79         st.start();
    94         bpmatch.init();
    80         bpmatch.init();
    95         bpmatch.start();
    81         bpmatch.start();
    96         st.stop();
    82         st.stop();
    97         
    83         
    98       }                 
       
    99       {
       
   100         MaxBipartiteMatching<LGraph> bpmatch(lgraph);
       
   101         
       
   102         lnt.start();
       
   103         bpmatch.init();
       
   104         bpmatch.start();
       
   105         lnt.stop();
       
   106         
       
   107       }
    84       }
       
    85                   
       
    86     }
   108 
    87 
   109       {
    88     cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
   110         typedef SwapBpUGraphAdaptor<LGraph> SGraph;
       
   111         SGraph sgraph(lgraph);
       
   112         MaxBipartiteMatching<SGraph> bpmatch(sgraph);
       
   113 
       
   114         lst.start();
       
   115         bpmatch.init();
       
   116         bpmatch.start();
       
   117         lst.stop();
       
   118         
       
   119       }
       
   120      }
       
   121 
       
   122     cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()
       
   123 	 << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;
       
   124 
    89 
   125   }
    90   }
   126 
    91 
   127   return 0;
    92   return 0;
   128 }
    93 }