author | alpar |
Tue, 28 Nov 2006 17:15:50 +0000 | |
changeset 2310 | 96cca167430a |
parent 2239 | 18c24fe93b99 |
child 2386 | 81b47fc5c444 |
permissions | -rw-r--r-- |
deba@2084 | 1 |
#include <cstdlib> |
deba@2084 | 2 |
#include <iostream> |
deba@2084 | 3 |
#include <sstream> |
deba@2084 | 4 |
|
deba@2084 | 5 |
#include <lemon/smart_graph.h> |
alpar@2239 | 6 |
#include <lemon/list_graph.h> |
deba@2084 | 7 |
|
deba@2084 | 8 |
#include <lemon/bpugraph_adaptor.h> |
deba@2084 | 9 |
#include <lemon/bipartite_matching.h> |
deba@2084 | 10 |
|
deba@2084 | 11 |
#include <lemon/graph_utils.h> |
deba@2084 | 12 |
#include <lemon/graph_to_eps.h> |
deba@2084 | 13 |
|
deba@2084 | 14 |
#include <lemon/time_measure.h> |
deba@2242 | 15 |
#include <lemon/random.h> |
deba@2084 | 16 |
|
deba@2084 | 17 |
using namespace std; |
deba@2084 | 18 |
using namespace lemon; |
deba@2084 | 19 |
|
deba@2084 | 20 |
typedef SmartBpUGraph Graph; |
alpar@2239 | 21 |
typedef ListBpUGraph LGraph; |
deba@2084 | 22 |
BPUGRAPH_TYPEDEFS(Graph); |
deba@2084 | 23 |
|
deba@2084 | 24 |
|
deba@2084 | 25 |
int main() { |
deba@2084 | 26 |
|
deba@2084 | 27 |
for (int k = 1; k < 100; ++k) { |
deba@2084 | 28 |
|
deba@2084 | 29 |
int n = k * 100; |
deba@2084 | 30 |
int m = (100 - k) * 100; |
deba@2084 | 31 |
int e = 20000; |
deba@2084 | 32 |
int s = 100; |
deba@2084 | 33 |
|
deba@2084 | 34 |
Timer nt(false), st(false); |
alpar@2239 | 35 |
Timer lnt(false), lst(false); |
deba@2084 | 36 |
|
deba@2084 | 37 |
for (int i = 0; i < s; ++i) { |
deba@2084 | 38 |
Graph graph; |
alpar@2239 | 39 |
LGraph lgraph; |
deba@2084 | 40 |
vector<Node> aNodes; |
deba@2084 | 41 |
vector<Node> bNodes; |
alpar@2239 | 42 |
vector<LGraph::Node> laNodes; |
alpar@2239 | 43 |
vector<LGraph::Node> lbNodes; |
deba@2084 | 44 |
|
deba@2084 | 45 |
for (int i = 0; i < n; ++i) { |
deba@2084 | 46 |
Node node = graph.addANode(); |
deba@2084 | 47 |
aNodes.push_back(node); |
alpar@2239 | 48 |
LGraph::Node lnode = lgraph.addANode(); |
alpar@2239 | 49 |
laNodes.push_back(lnode); |
deba@2084 | 50 |
} |
deba@2084 | 51 |
for (int i = 0; i < m; ++i) { |
deba@2084 | 52 |
Node node = graph.addBNode(); |
deba@2084 | 53 |
bNodes.push_back(node); |
alpar@2239 | 54 |
LGraph::Node lnode = lgraph.addBNode(); |
alpar@2239 | 55 |
lbNodes.push_back(lnode); |
deba@2084 | 56 |
} |
deba@2084 | 57 |
for (int i = 0; i < e; ++i) { |
alpar@2239 | 58 |
int a,b; |
deba@2242 | 59 |
Node aNode = aNodes[a=rnd[n]]; |
deba@2242 | 60 |
Node bNode = bNodes[b=rnd[m]]; |
deba@2084 | 61 |
graph.addEdge(aNode, bNode); |
alpar@2239 | 62 |
LGraph::Node laNode = laNodes[a]; |
alpar@2239 | 63 |
LGraph::Node lbNode = lbNodes[b]; |
alpar@2239 | 64 |
lgraph.addEdge(laNode, lbNode); |
deba@2084 | 65 |
} |
deba@2084 | 66 |
|
deba@2084 | 67 |
{ |
deba@2084 | 68 |
MaxBipartiteMatching<Graph> bpmatch(graph); |
deba@2084 | 69 |
|
deba@2084 | 70 |
nt.start(); |
deba@2084 | 71 |
bpmatch.init(); |
deba@2084 | 72 |
bpmatch.start(); |
deba@2084 | 73 |
nt.stop(); |
deba@2084 | 74 |
|
deba@2084 | 75 |
} |
deba@2084 | 76 |
|
deba@2084 | 77 |
{ |
deba@2084 | 78 |
typedef SwapBpUGraphAdaptor<Graph> SGraph; |
deba@2084 | 79 |
SGraph sgraph(graph); |
deba@2084 | 80 |
MaxBipartiteMatching<SGraph> bpmatch(sgraph); |
deba@2084 | 81 |
|
deba@2084 | 82 |
st.start(); |
deba@2084 | 83 |
bpmatch.init(); |
deba@2084 | 84 |
bpmatch.start(); |
deba@2084 | 85 |
st.stop(); |
deba@2084 | 86 |
|
alpar@2239 | 87 |
} |
alpar@2239 | 88 |
{ |
alpar@2239 | 89 |
MaxBipartiteMatching<LGraph> bpmatch(lgraph); |
alpar@2239 | 90 |
|
alpar@2239 | 91 |
lnt.start(); |
alpar@2239 | 92 |
bpmatch.init(); |
alpar@2239 | 93 |
bpmatch.start(); |
alpar@2239 | 94 |
lnt.stop(); |
alpar@2239 | 95 |
|
deba@2084 | 96 |
} |
deba@2084 | 97 |
|
alpar@2239 | 98 |
{ |
alpar@2239 | 99 |
typedef SwapBpUGraphAdaptor<LGraph> SGraph; |
alpar@2239 | 100 |
SGraph sgraph(lgraph); |
alpar@2239 | 101 |
MaxBipartiteMatching<SGraph> bpmatch(sgraph); |
alpar@2239 | 102 |
|
alpar@2239 | 103 |
lst.start(); |
alpar@2239 | 104 |
bpmatch.init(); |
alpar@2239 | 105 |
bpmatch.start(); |
alpar@2239 | 106 |
lst.stop(); |
alpar@2239 | 107 |
|
alpar@2239 | 108 |
} |
alpar@2239 | 109 |
} |
alpar@2239 | 110 |
|
alpar@2239 | 111 |
cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() |
alpar@2239 | 112 |
<< ' ' << lnt.realTime() << ' ' << lst.realTime()<< endl; |
deba@2084 | 113 |
|
deba@2084 | 114 |
} |
deba@2084 | 115 |
|
deba@2084 | 116 |
return 0; |
deba@2084 | 117 |
} |