COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/swap_bipartite_bench.cc @ 2242:16523135943d

Last change on this file since 2242:16523135943d was 2242:16523135943d, checked in by Balazs Dezso, 17 years ago

New random interface
Switching to the new interface

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