COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/swap_bipartite_bench.cc @ 2391:14a343be7a5a

Last change on this file since 2391:14a343be7a5a was 2391:14a343be7a5a, checked in by Alpar Juttner, 17 years ago

Happy New Year to all source files!

File size: 3.1 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <cstdlib>
20#include <iostream>
21#include <sstream>
22
23#include <lemon/smart_graph.h>
24#include <lemon/list_graph.h>
25
26#include <lemon/bpugraph_adaptor.h>
27#include <lemon/bipartite_matching.h>
28
29#include <lemon/graph_utils.h>
30#include <lemon/graph_to_eps.h>
31
32#include <lemon/time_measure.h>
33#include <lemon/random.h>
34
35using namespace std;
36using namespace lemon;
37
38typedef SmartBpUGraph Graph;
39typedef ListBpUGraph LGraph;
40BPUGRAPH_TYPEDEFS(Graph);
41
42
43int main() {
44
45  for (int k = 1; k < 100; ++k) {
46   
47    int n = k * 100;
48    int m = (100 - k) * 100;
49    int e = 20000;
50    int s = 100;
51   
52    Timer nt(false), st(false);
53    Timer lnt(false), lst(false);
54   
55    for (int i = 0; i < s; ++i) {
56      Graph graph;
57      LGraph lgraph;
58      vector<Node> aNodes;
59      vector<Node> bNodes; 
60      vector<LGraph::Node> laNodes;
61      vector<LGraph::Node> lbNodes; 
62     
63      for (int j = 0; j < n; ++j) {
64        Node node = graph.addANode();
65        aNodes.push_back(node);
66        LGraph::Node lnode = lgraph.addANode();
67        laNodes.push_back(lnode);
68      }
69      for (int j = 0; j < m; ++j) {
70        Node node = graph.addBNode();
71        bNodes.push_back(node);
72        LGraph::Node lnode = lgraph.addBNode();
73        lbNodes.push_back(lnode);
74      }
75      for (int j = 0; j < e; ++j) {
76        int a,b;
77        Node aNode = aNodes[a=rnd[n]];
78        Node bNode = bNodes[b=rnd[m]];
79        graph.addEdge(aNode, bNode);
80        LGraph::Node laNode = laNodes[a];
81        LGraph::Node lbNode = lbNodes[b];
82        lgraph.addEdge(laNode, lbNode);
83      }
84
85      {
86        MaxBipartiteMatching<Graph> bpmatch(graph);
87       
88        nt.start();
89        bpmatch.init();
90        bpmatch.start();
91        nt.stop();
92       
93      }
94
95      {
96        typedef SwapBpUGraphAdaptor<Graph> SGraph;
97        SGraph sgraph(graph);
98        MaxBipartiteMatching<SGraph> bpmatch(sgraph);
99
100        st.start();
101        bpmatch.init();
102        bpmatch.start();
103        st.stop();
104       
105      }                 
106      {
107        MaxBipartiteMatching<LGraph> bpmatch(lgraph);
108       
109        lnt.start();
110        bpmatch.init();
111        bpmatch.start();
112        lnt.stop();
113       
114      }
115
116      {
117        typedef SwapBpUGraphAdaptor<LGraph> SGraph;
118        SGraph sgraph(lgraph);
119        MaxBipartiteMatching<SGraph> bpmatch(sgraph);
120
121        lst.start();
122        bpmatch.init();
123        bpmatch.start();
124        lst.stop();
125       
126      }
127     }
128
129    cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime()
130         << ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl;
131
132  }
133
134  return 0;
135}
Note: See TracBrowser for help on using the repository browser.