COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/swap_bipartite_bench.cc

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 16 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 3.1 KB
RevLine 
[2391]1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
[2553]5 * Copyright (C) 2003-2008
[2391]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
[2084]19#include <cstdlib>
20#include <iostream>
21#include <sstream>
22
23#include <lemon/smart_graph.h>
[2239]24#include <lemon/list_graph.h>
[2084]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>
[2242]33#include <lemon/random.h>
[2084]34
35using namespace std;
36using namespace lemon;
37
38typedef SmartBpUGraph Graph;
[2239]39typedef ListBpUGraph LGraph;
[2084]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);
[2239]53    Timer lnt(false), lst(false);
[2084]54   
55    for (int i = 0; i < s; ++i) {
56      Graph graph;
[2239]57      LGraph lgraph;
[2084]58      vector<Node> aNodes;
59      vector<Node> bNodes; 
[2239]60      vector<LGraph::Node> laNodes;
61      vector<LGraph::Node> lbNodes; 
[2084]62     
[2386]63      for (int j = 0; j < n; ++j) {
[2084]64        Node node = graph.addANode();
65        aNodes.push_back(node);
[2239]66        LGraph::Node lnode = lgraph.addANode();
67        laNodes.push_back(lnode);
[2084]68      }
[2386]69      for (int j = 0; j < m; ++j) {
[2084]70        Node node = graph.addBNode();
71        bNodes.push_back(node);
[2239]72        LGraph::Node lnode = lgraph.addBNode();
73        lbNodes.push_back(lnode);
[2084]74      }
[2386]75      for (int j = 0; j < e; ++j) {
[2239]76        int a,b;
[2242]77        Node aNode = aNodes[a=rnd[n]];
78        Node bNode = bNodes[b=rnd[m]];
[2084]79        graph.addEdge(aNode, bNode);
[2239]80        LGraph::Node laNode = laNodes[a];
81        LGraph::Node lbNode = lbNodes[b];
82        lgraph.addEdge(laNode, lbNode);
[2084]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       
[2239]105      }                 
106      {
107        MaxBipartiteMatching<LGraph> bpmatch(lgraph);
108       
109        lnt.start();
110        bpmatch.init();
111        bpmatch.start();
112        lnt.stop();
113       
[2084]114      }
115
[2239]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;
[2084]131
132  }
133
134  return 0;
135}
Note: See TracBrowser for help on using the repository browser.