author | athos |
Mon, 17 Jul 2006 09:10:19 +0000 | |
changeset 2145 | 73e0c8207e11 |
parent 2084 | 59769591eb60 |
child 2207 | 75a29ac69c19 |
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> |
deba@2084 | 6 |
|
deba@2084 | 7 |
#include <lemon/bpugraph_adaptor.h> |
deba@2084 | 8 |
#include <lemon/bipartite_matching.h> |
deba@2084 | 9 |
|
deba@2084 | 10 |
#include <lemon/graph_utils.h> |
deba@2084 | 11 |
#include <lemon/xy.h> |
deba@2084 | 12 |
#include <lemon/graph_to_eps.h> |
deba@2084 | 13 |
|
deba@2084 | 14 |
#include <lemon/time_measure.h> |
deba@2084 | 15 |
|
deba@2084 | 16 |
using namespace std; |
deba@2084 | 17 |
using namespace lemon; |
deba@2084 | 18 |
|
deba@2084 | 19 |
typedef SmartBpUGraph Graph; |
deba@2084 | 20 |
BPUGRAPH_TYPEDEFS(Graph); |
deba@2084 | 21 |
|
deba@2084 | 22 |
int _urandom_init() { |
deba@2084 | 23 |
int seed = time(0); |
deba@2084 | 24 |
srand(seed); |
deba@2084 | 25 |
return seed; |
deba@2084 | 26 |
} |
deba@2084 | 27 |
|
deba@2084 | 28 |
int urandom(int n) { |
deba@2084 | 29 |
static int seed = _urandom_init(); |
deba@2130 | 30 |
ignore_unused_variable_warning(seed); |
deba@2084 | 31 |
return (int)(rand() / (1.0 + RAND_MAX) * n); |
deba@2084 | 32 |
} |
deba@2084 | 33 |
|
deba@2084 | 34 |
int main() { |
deba@2084 | 35 |
|
deba@2084 | 36 |
for (int k = 1; k < 100; ++k) { |
deba@2084 | 37 |
|
deba@2084 | 38 |
int n = k * 100; |
deba@2084 | 39 |
int m = (100 - k) * 100; |
deba@2084 | 40 |
int e = 20000; |
deba@2084 | 41 |
int s = 100; |
deba@2084 | 42 |
|
deba@2084 | 43 |
Timer nt(false), st(false); |
deba@2084 | 44 |
|
deba@2084 | 45 |
for (int i = 0; i < s; ++i) { |
deba@2084 | 46 |
Graph graph; |
deba@2084 | 47 |
vector<Node> aNodes; |
deba@2084 | 48 |
vector<Node> bNodes; |
deba@2084 | 49 |
|
deba@2084 | 50 |
for (int i = 0; i < n; ++i) { |
deba@2084 | 51 |
Node node = graph.addANode(); |
deba@2084 | 52 |
aNodes.push_back(node); |
deba@2084 | 53 |
} |
deba@2084 | 54 |
for (int i = 0; i < m; ++i) { |
deba@2084 | 55 |
Node node = graph.addBNode(); |
deba@2084 | 56 |
bNodes.push_back(node); |
deba@2084 | 57 |
} |
deba@2084 | 58 |
for (int i = 0; i < e; ++i) { |
deba@2084 | 59 |
Node aNode = aNodes[urandom(n)]; |
deba@2084 | 60 |
Node bNode = bNodes[urandom(m)]; |
deba@2084 | 61 |
graph.addEdge(aNode, bNode); |
deba@2084 | 62 |
} |
deba@2084 | 63 |
|
deba@2084 | 64 |
{ |
deba@2084 | 65 |
MaxBipartiteMatching<Graph> bpmatch(graph); |
deba@2084 | 66 |
|
deba@2084 | 67 |
nt.start(); |
deba@2084 | 68 |
bpmatch.init(); |
deba@2084 | 69 |
bpmatch.start(); |
deba@2084 | 70 |
nt.stop(); |
deba@2084 | 71 |
|
deba@2084 | 72 |
} |
deba@2084 | 73 |
|
deba@2084 | 74 |
{ |
deba@2084 | 75 |
typedef SwapBpUGraphAdaptor<Graph> SGraph; |
deba@2084 | 76 |
SGraph sgraph(graph); |
deba@2084 | 77 |
MaxBipartiteMatching<SGraph> bpmatch(sgraph); |
deba@2084 | 78 |
|
deba@2084 | 79 |
st.start(); |
deba@2084 | 80 |
bpmatch.init(); |
deba@2084 | 81 |
bpmatch.start(); |
deba@2084 | 82 |
st.stop(); |
deba@2084 | 83 |
|
deba@2084 | 84 |
} |
deba@2084 | 85 |
|
deba@2084 | 86 |
} |
deba@2084 | 87 |
|
deba@2084 | 88 |
cout << k * 100 << ' ' << nt.realTime() << ' ' << st.realTime() << endl; |
deba@2084 | 89 |
|
deba@2084 | 90 |
} |
deba@2084 | 91 |
|
deba@2084 | 92 |
return 0; |
deba@2084 | 93 |
} |