COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/swap_bipartite_bench.cc @ 2239:18c24fe93b99

Last change on this file since 2239:18c24fe93b99 was 2239:18c24fe93b99, checked in by Alpar Juttner, 17 years ago

Turn off 32bit specific tests.

File size: 2.7 KB
Line 
1#include <cstdlib>
2#include <iostream>
3#include <sstream>
4
5#include <lemon/smart_graph.h>
6#include <lemon/list_graph.h>
7
8#include <lemon/bpugraph_adaptor.h>
9#include <lemon/bipartite_matching.h>
10
11#include <lemon/graph_utils.h>
12#include <lemon/graph_to_eps.h>
13
14#include <lemon/time_measure.h>
15
16using namespace std;
17using namespace lemon;
18
19typedef SmartBpUGraph Graph;
20typedef ListBpUGraph LGraph;
21BPUGRAPH_TYPEDEFS(Graph);
22
23int _urandom_init() {
24  int seed = time(0);
25  srand(seed);
26  return seed;
27}
28
29int urandom(int n) {
30  static int seed = _urandom_init();
31  ignore_unused_variable_warning(seed);
32  return (int)(rand() / (1.0 + RAND_MAX) * n);
33}
34
35int main() {
36
37  for (int k = 1; k < 100; ++k) {
38   
39    int n = k * 100;
40    int m = (100 - k) * 100;
41    int e = 20000;
42    int s = 100;
43   
44    Timer nt(false), st(false);
45    Timer lnt(false), lst(false);
46   
47    for (int i = 0; i < s; ++i) {
48      Graph graph;
49      LGraph lgraph;
50      vector<Node> aNodes;
51      vector<Node> bNodes; 
52      vector<LGraph::Node> laNodes;
53      vector<LGraph::Node> lbNodes; 
54     
55      for (int i = 0; i < n; ++i) {
56        Node node = graph.addANode();
57        aNodes.push_back(node);
58        LGraph::Node lnode = lgraph.addANode();
59        laNodes.push_back(lnode);
60      }
61      for (int i = 0; i < m; ++i) {
62        Node node = graph.addBNode();
63        bNodes.push_back(node);
64        LGraph::Node lnode = lgraph.addBNode();
65        lbNodes.push_back(lnode);
66      }
67      for (int i = 0; i < e; ++i) {
68        int a,b;
69        Node aNode = aNodes[a=urandom(n)];
70        Node bNode = bNodes[b=urandom(m)];
71        graph.addEdge(aNode, bNode);
72        LGraph::Node laNode = laNodes[a];
73        LGraph::Node lbNode = lbNodes[b];
74        lgraph.addEdge(laNode, lbNode);
75      }
76
77      {
78        MaxBipartiteMatching<Graph> bpmatch(graph);
79       
80        nt.start();
81        bpmatch.init();
82        bpmatch.start();
83        nt.stop();
84       
85      }
86
87      {
88        typedef SwapBpUGraphAdaptor<Graph> SGraph;
89        SGraph sgraph(graph);
90        MaxBipartiteMatching<SGraph> bpmatch(sgraph);
91
92        st.start();
93        bpmatch.init();
94        bpmatch.start();
95        st.stop();
96       
97      }                 
98      {
99        MaxBipartiteMatching<LGraph> bpmatch(lgraph);
100       
101        lnt.start();
102        bpmatch.init();
103        bpmatch.start();
104        lnt.stop();
105       
106      }
107
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;
123
124  }
125
126  return 0;
127}
Note: See TracBrowser for help on using the repository browser.