deba@2084: #include <cstdlib>
deba@2084: #include <iostream>
deba@2084: #include <sstream>
deba@2084: 
deba@2084: #include <lemon/smart_graph.h>
deba@2084: 
deba@2084: #include <lemon/bpugraph_adaptor.h>
deba@2084: #include <lemon/bipartite_matching.h>
deba@2084: 
deba@2084: #include <lemon/graph_utils.h>
deba@2084: #include <lemon/xy.h>
deba@2084: #include <lemon/graph_to_eps.h>
deba@2084: 
deba@2084: #include <lemon/time_measure.h>
deba@2084: 
deba@2084: using namespace std;
deba@2084: using namespace lemon;
deba@2084: 
deba@2084: typedef SmartBpUGraph Graph;
deba@2084: BPUGRAPH_TYPEDEFS(Graph);
deba@2084: 
deba@2084: int _urandom_init() {
deba@2084:   int seed = time(0);
deba@2084:   srand(seed);
deba@2084:   return seed;
deba@2084: }
deba@2084: 
deba@2084: int urandom(int n) {
deba@2084:   static int seed = _urandom_init();
deba@2130:   ignore_unused_variable_warning(seed);
deba@2084:   return (int)(rand() / (1.0 + RAND_MAX) * n);
deba@2084: }
deba@2084: 
deba@2084: int main() {
deba@2084: 
deba@2084:   for (int k = 1; k < 100; ++k) {
deba@2084:     
deba@2084:     int n = k * 100;
deba@2084:     int m = (100 - k) * 100;
deba@2084:     int e = 20000;
deba@2084:     int s = 100;
deba@2084:     
deba@2084:     Timer nt(false), st(false);
deba@2084:     
deba@2084:     for (int i = 0; i < s; ++i) {
deba@2084:       Graph graph;
deba@2084:       vector<Node> aNodes;
deba@2084:       vector<Node> bNodes;  
deba@2084:       
deba@2084:       for (int i = 0; i < n; ++i) {
deba@2084:         Node node = graph.addANode();
deba@2084:         aNodes.push_back(node);
deba@2084:       }
deba@2084:       for (int i = 0; i < m; ++i) {
deba@2084:         Node node = graph.addBNode();
deba@2084:         bNodes.push_back(node);
deba@2084:       }
deba@2084:       for (int i = 0; i < e; ++i) {
deba@2084:         Node aNode = aNodes[urandom(n)];
deba@2084:         Node bNode = bNodes[urandom(m)];
deba@2084:         graph.addEdge(aNode, bNode);
deba@2084:       }
deba@2084: 
deba@2084:       {
deba@2084:         MaxBipartiteMatching<Graph> bpmatch(graph);
deba@2084:         
deba@2084:         nt.start();
deba@2084:         bpmatch.init();
deba@2084:         bpmatch.start();
deba@2084:         nt.stop();
deba@2084:         
deba@2084:       }
deba@2084: 
deba@2084:       {
deba@2084:         typedef SwapBpUGraphAdaptor<Graph> SGraph;
deba@2084:         SGraph sgraph(graph);
deba@2084:         MaxBipartiteMatching<SGraph> bpmatch(sgraph);
deba@2084: 
deba@2084:         st.start();
deba@2084:         bpmatch.init();
deba@2084:         bpmatch.start();
deba@2084:         st.stop();
deba@2084:         
deba@2084:       }
deba@2084:                   
deba@2084:     }
deba@2084: 
deba@2084:     cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
deba@2084: 
deba@2084:   }
deba@2084: 
deba@2084:   return 0;
deba@2084: }