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