COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/swap_bipartite_bench.cc @ 2118:54350d5c316a

Last change on this file since 2118:54350d5c316a was 2084:59769591eb60, checked in by Balazs Dezso, 18 years ago

Documentation improvements

Rearrangements:

IO modules
Algorithms

New documentation:

SwapBpUGraphAdaptor

Demos:

strongly_connected_orientation.cc

Benchmarks:

swap_bipartite_bench.cc

File size: 1.8 KB
Line 
1#include <cstdlib>
2#include <iostream>
3#include <sstream>
4
5#include <lemon/smart_graph.h>
6
7#include <lemon/bpugraph_adaptor.h>
8#include <lemon/bipartite_matching.h>
9
10#include <lemon/graph_utils.h>
11#include <lemon/xy.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;
20BPUGRAPH_TYPEDEFS(Graph);
21
22int _urandom_init() {
23  int seed = time(0);
24  srand(seed);
25  return seed;
26}
27
28int urandom(int n) {
29  static int seed = _urandom_init();
30  return (int)(rand() / (1.0 + RAND_MAX) * n);
31}
32
33int main() {
34
35  for (int k = 1; k < 100; ++k) {
36   
37    int n = k * 100;
38    int m = (100 - k) * 100;
39    int e = 20000;
40    int s = 100;
41   
42    Timer nt(false), st(false);
43   
44    for (int i = 0; i < s; ++i) {
45      Graph graph;
46      vector<Node> aNodes;
47      vector<Node> bNodes; 
48     
49      for (int i = 0; i < n; ++i) {
50        Node node = graph.addANode();
51        aNodes.push_back(node);
52      }
53      for (int i = 0; i < m; ++i) {
54        Node node = graph.addBNode();
55        bNodes.push_back(node);
56      }
57      for (int i = 0; i < e; ++i) {
58        Node aNode = aNodes[urandom(n)];
59        Node bNode = bNodes[urandom(m)];
60        graph.addEdge(aNode, bNode);
61      }
62
63      {
64        MaxBipartiteMatching<Graph> bpmatch(graph);
65       
66        nt.start();
67        bpmatch.init();
68        bpmatch.start();
69        nt.stop();
70       
71      }
72
73      {
74        typedef SwapBpUGraphAdaptor<Graph> SGraph;
75        SGraph sgraph(graph);
76        MaxBipartiteMatching<SGraph> bpmatch(sgraph);
77
78        st.start();
79        bpmatch.init();
80        bpmatch.start();
81        st.stop();
82       
83      }
84                 
85    }
86
87    cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl;
88
89  }
90
91  return 0;
92}
Note: See TracBrowser for help on using the repository browser.