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