COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/swap_bipartite_bench.cc @ 2207:75a29ac69c19

Last change on this file since 2207:75a29ac69c19 was 2207:75a29ac69c19, checked in by Alpar Juttner, 14 years ago

xy -> dim2::Point

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