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 2207 75a29ac69c19
parent 2130 244e108de26f
child 2208 37b5c870a953
equal deleted inserted replaced
1:317932c2ec83 2:1dd58b0542eb 
     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>
 
    11 #include <lemon/xy.h>
 
    12 #include <lemon/dim2.h>
 
    12 #include <lemon/graph_to_eps.h>
 
    13 #include <lemon/graph_to_eps.h>
 
    13 
    14 
    14 #include <lemon/time_measure.h>
 
    15 #include <lemon/time_measure.h>
 
    15 
    16 
    16 using namespace std;
 
    17 using namespace std;
 
    17 using namespace lemon;
 
    18 using namespace lemon;
 
    18 
    19 
    19 typedef SmartBpUGraph Graph;
 
    20 typedef SmartBpUGraph Graph;
 
       
    21 typedef ListBpUGraph LGraph;
 
    20 BPUGRAPH_TYPEDEFS(Graph);
 
    22 BPUGRAPH_TYPEDEFS(Graph);
 
    21 
    23 
    22 int _urandom_init() {
 
    24 int _urandom_init() {
 
    23   int seed = time(0);
 
    25   int seed = time(0);
 
    24   srand(seed);
 
    26   srand(seed);
 
    39     int m = (100 - k) * 100;
 
    41     int m = (100 - k) * 100;
 
    40     int e = 20000;
 
    42     int e = 20000;
 
    41     int s = 100;
 
    43     int s = 100;
 
    42     
    44     
    43     Timer nt(false), st(false);
 
    45     Timer nt(false), st(false);
 
       
    46     Timer lnt(false), lst(false);
 
    44     
    47     
    45     for (int i = 0; i < s; ++i) {
 
    48     for (int i = 0; i < s; ++i) {
 
    46       Graph graph;
 
    49       Graph graph;
 
       
    50       LGraph lgraph;
 
    47       vector<Node> aNodes;
 
    51       vector<Node> aNodes;
 
    48       vector<Node> bNodes;  
    52       vector<Node> bNodes;  
       
    53       vector<LGraph::Node> laNodes;
 
       
    54       vector<LGraph::Node> lbNodes;  
    49       
    55       
    50       for (int i = 0; i < n; ++i) {
 
    56       for (int i = 0; i < n; ++i) {
 
    51         Node node = graph.addANode();
 
    57         Node node = graph.addANode();
 
    52         aNodes.push_back(node);
 
    58         aNodes.push_back(node);
 
       
    59         LGraph::Node lnode = lgraph.addANode();
 
       
    60         laNodes.push_back(lnode);
 
    53       }
 
    61       }
 
    54       for (int i = 0; i < m; ++i) {
 
    62       for (int i = 0; i < m; ++i) {
 
    55         Node node = graph.addBNode();
 
    63         Node node = graph.addBNode();
 
    56         bNodes.push_back(node);
 
    64         bNodes.push_back(node);
 
       
    65         LGraph::Node lnode = lgraph.addBNode();
 
       
    66         lbNodes.push_back(lnode);
 
    57       }
 
    67       }
 
    58       for (int i = 0; i < e; ++i) {
 
    68       for (int i = 0; i < e; ++i) {
 
    59         Node aNode = aNodes[urandom(n)];
 
    69         int a,b;
 
    60         Node bNode = bNodes[urandom(m)];
 
    70 	Node aNode = aNodes[a=urandom(n)];
 
       
    71         Node bNode = bNodes[b=urandom(m)];
 
    61         graph.addEdge(aNode, bNode);
 
    72         graph.addEdge(aNode, bNode);
 
       
    73 	LGraph::Node laNode = laNodes[a];
 
       
    74         LGraph::Node lbNode = lbNodes[b];
 
       
    75         lgraph.addEdge(laNode, lbNode);
 
    62       }
 
    76       }
 
    63 
    77 
    64       {
 
    78       {
 
    65         MaxBipartiteMatching<Graph> bpmatch(graph);
 
    79         MaxBipartiteMatching<Graph> bpmatch(graph);
 
    66         
    80         
    79         st.start();
 
    93         st.start();
 
    80         bpmatch.init();
 
    94         bpmatch.init();
 
    81         bpmatch.start();
 
    95         bpmatch.start();
 
    82         st.stop();
 
    96         st.stop();
 
    83         
    97         
       
    98       }                 
       
    99       {
 
       
   100         MaxBipartiteMatching<LGraph> bpmatch(lgraph);
 
       
   101         
       
   102         lnt.start();
 
       
   103         bpmatch.init();
 
       
   104         bpmatch.start();
 
       
   105         lnt.stop();
 
       
   106         
    84       }
 
   107       }
 
    85                   
       
    86     }
 
       
    87 
   108 
    88     cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
 
   109       {
 
       
   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;
 
    89 
   124 
    90   }
 
   125   }
 
    91 
   126 
    92   return 0;
 
   127   return 0;
 
    93 }
 
   128 }
lemon-0.x