1.1 --- a/benchmark/Makefile.am Thu Jan 11 21:22:39 2007 +0000
1.2 +++ b/benchmark/Makefile.am Thu Jan 11 21:27:51 2007 +0000
1.3 @@ -14,7 +14,8 @@
1.4 benchmark/radix_sort-bench \
1.5 benchmark/swap_bipartite_bench \
1.6 benchmark/random_bench \
1.7 - benchmark/edge_lookup
1.8 + benchmark/edge_lookup \
1.9 + benchmark/min_cut
1.10
1.11 endif WANT_BENCHMARK
1.12
1.13 @@ -31,3 +32,5 @@
1.14 benchmark_random_bench_SOURCES = benchmark/random_bench.cc
1.15
1.16 benchmark_edge_lookup_SOURCES = benchmark/edge_lookup.cc
1.17 +
1.18 +benchmark_min_cut_SOURCES = benchmark/min_cut.cc
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/benchmark/min_cut.cc Thu Jan 11 21:27:51 2007 +0000
2.3 @@ -0,0 +1,169 @@
2.4 +#include <lemon/list_graph.h>
2.5 +
2.6 +#include <lemon/hao_orlin.h>
2.7 +#include <lemon/nagamochi_ibaraki.h>
2.8 +#include <lemon/time_measure.h>
2.9 +
2.10 +using namespace lemon;
2.11 +
2.12 +#include "min_cut_graphs.h"
2.13 +
2.14 +
2.15 +void testRegUGraph();
2.16 +void testNoiUGraph();
2.17 +void testBikeWheelUGraph();
2.18 +
2.19 +int main() {
2.20 + testRegUGraph();
2.21 + testNoiUGraph();
2.22 + testBikeWheelUGraph();
2.23 + return 0;
2.24 +}
2.25 +
2.26 +//#define int long long
2.27 +
2.28 +
2.29 +int cutValue(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c,
2.30 + const ListUGraph::NodeMap<bool>& n) {
2.31 + int v = 0;
2.32 + for (ListUGraph::UEdgeIt e(g); e != INVALID; ++e) {
2.33 + if (n[g.source(e)] != n[g.target(e)]) {
2.34 + v += c[e];
2.35 + }
2.36 + }
2.37 + return v;
2.38 +}
2.39 +
2.40 +int cutSize(const ListUGraph& g, const ListUGraph::NodeMap<bool>& nm) {
2.41 + int m = 0;
2.42 + for (ListUGraph::NodeIt n(g); n != INVALID; ++n) {
2.43 + if (nm[n]) {
2.44 + ++m;
2.45 + }
2.46 + }
2.47 + return m;
2.48 +}
2.49 +
2.50 +int testNI(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
2.51 + TimeReport tr("Nagamochi-Ibaraki : ");
2.52 + NagamochiIbaraki<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
2.53 + alg.run();
2.54 + ListUGraph::NodeMap<bool> n(g);
2.55 + alg.minCut(n);
2.56 + std::cout << "Check : " << cutValue(g, c, n) << ' '
2.57 + << cutSize(g, n) << std::endl;
2.58 + return alg.minCut();
2.59 +}
2.60 +
2.61 +int testHO(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
2.62 + TimeReport tr("Hao-Orlin : ");
2.63 + HaoOrlin<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
2.64 + alg.init();
2.65 + alg.calculateOut();
2.66 + ListUGraph::NodeMap<bool> n(g);
2.67 + alg.minCut(n);
2.68 + std::cout << "Check : " << cutValue(g, c, n) << ' '
2.69 + << cutSize(g, n) << std::endl;
2.70 + return alg.minCut();
2.71 +}
2.72 +
2.73 +void testBikeWheelUGraph(int n) {
2.74 + ListUGraph g;
2.75 + ListUGraph::UEdgeMap<int> c(g);
2.76 + genBikeWheelUGraph(g, c, n);
2.77 + std::cout << "Node number : " << n << std::endl;
2.78 + std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
2.79 + std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
2.80 +}
2.81 +
2.82 +void testBikeWheelUGraph() {
2.83 + std::cout << "BikeWheelUGraph : " << std::endl;
2.84 + for (int k = 10; k <= 13; ++k) {
2.85 + int n = 1 << k;
2.86 + testBikeWheelUGraph(n);
2.87 + }
2.88 +}
2.89 +
2.90 +void testNoiUGraph(int n, int d, int k, int p) {
2.91 + ListUGraph g;
2.92 + ListUGraph::UEdgeMap<int> c(g);
2.93 + genNoiUGraph(g, c, n, d, k, p);
2.94 + std::cout << "Node number : " << n << std::endl;
2.95 + std::cout << "Density : " << d << std::endl;
2.96 + std::cout << "Tight components : " << k << std::endl;
2.97 + std::cout << "Scale : " << p << std::endl;
2.98 + std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
2.99 + std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
2.100 +}
2.101 +
2.102 +
2.103 +void testNoiUGraph() {
2.104 + std::cout << "NoiUGraph : " << std::endl;
2.105 + std::cout << "Serial 1 : " << std::endl;
2.106 + for (int n = 300; n <= 1000; n += 100) {
2.107 + testNoiUGraph(n, 50, 1, n);
2.108 + }
2.109 + std::cout << "Serial 2 : " << std::endl;
2.110 + for (int n = 300; n <= 1000; n += 100) {
2.111 + testNoiUGraph(n, 50, 2, n);
2.112 + }
2.113 + std::cout << "Serial 3 : " << std::endl;
2.114 + int da3[] = { 5, 10, 25, 50, 75, 100 };
2.115 + int dn3 = sizeof(da3) / sizeof(da3[0]);
2.116 + for (int d = 0; d < dn3; ++d) {
2.117 + testNoiUGraph(1000, da3[d], 1, 1000);
2.118 + }
2.119 + std::cout << "Serial 4 : " << std::endl;
2.120 + for (int d = 0; d < dn3; ++d) {
2.121 + testNoiUGraph(1000, da3[d], 2, 1000);
2.122 + }
2.123 + std::cout << "Serial 5 : " << std::endl;
2.124 + int ka5[] = {1, 2, 3, 5, 7, 10, 20, 30, 33, 35,
2.125 + 40, 50, 100, 200, 300, 400, 500};
2.126 + int kn5 = sizeof(ka5) / sizeof(ka5[0]);
2.127 + for (int k = 0; k < kn5; ++k) {
2.128 + testNoiUGraph(1000, 50, ka5[k], 1000);
2.129 + }
2.130 + std::cout << "Serial 6 : " << std::endl;
2.131 + int pa6[] = { 5000, 2000, 1000, 500, 250, 100, 50, 10, 1};
2.132 + int pn6 = sizeof(pa6) / sizeof(pa6[0]);
2.133 + for (int p = 0; p < pn6; ++p) {
2.134 + testNoiUGraph(1000, 50, 2, pa6[p]);
2.135 + }
2.136 +
2.137 +}
2.138 +
2.139 +void testRegUGraph(int n, int d) {
2.140 + ListUGraph g;
2.141 + ListUGraph::UEdgeMap<int> c(g);
2.142 + genRegUGraph(g, c, n, d);
2.143 + std::cout << "Node number : " << n << std::endl;
2.144 + std::cout << "Number of cycles : " << d << std::endl;
2.145 + std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
2.146 + std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
2.147 +}
2.148 +
2.149 +void testRegUGraph() {
2.150 + std::cout << "RegUGraph : " << std::endl;
2.151 + std::cout << "Serial 1 : " << std::endl;
2.152 + int da1[] = { 1, 3, 10, 33, 100, 333, 1000};
2.153 + int dn1 = sizeof(da1) / sizeof(da1[0]);
2.154 + for (int d = 0; d < dn1; ++d) {
2.155 + testRegUGraph(1001, da1[d]);
2.156 + }
2.157 + std::cout << "Serial 2 : " << std::endl;
2.158 + int na2[] = { 50, 100, 200, 400, 800};
2.159 + int nn2 = sizeof(na2) / sizeof(na2[0]);
2.160 + for (int n = 0; n < nn2; ++n) {
2.161 + testRegUGraph(na2[n], 50);
2.162 + }
2.163 + std::cout << "Serial 3 : " << std::endl;
2.164 + for (int n = 8; n <= 14; ++n) {
2.165 + testRegUGraph(1 << n, 2);
2.166 + }
2.167 + std::cout << "Serial 4 : " << std::endl;
2.168 + for (int n = 7; n <= 11; ++n) {
2.169 + testRegUGraph(1 << n, 1 << (n - 4));
2.170 + }
2.171 +}
2.172 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/benchmark/min_cut_graphs.h Thu Jan 11 21:27:51 2007 +0000
3.3 @@ -0,0 +1,82 @@
3.4 +// -*- C++ -*-
3.5 +#include <lemon/random.h>
3.6 +
3.7 +
3.8 +template <typename UGraph, typename CapacityMap>
3.9 +void genNoiUGraph(UGraph& g, CapacityMap& c,
3.10 + int n, int d, int k, int p) {
3.11 + std::vector<typename UGraph::Node> nodes(n);
3.12 + for (int i = 0; i < n; ++i) {
3.13 + nodes[i] = g.addNode();
3.14 + }
3.15 + typename UGraph::template NodeMap<int> comp(g);
3.16 + for (int i = 0; i < n; ++i) {
3.17 + comp[nodes[i]] = rnd[k];
3.18 + }
3.19 + int m = (n * (n - 1) * d) / 200;
3.20 + for (int i = 0; i < m; ++i) {
3.21 + int s = rnd[n], t = rnd[n];
3.22 + c[g.addEdge(nodes[s], nodes[t])] =
3.23 + rnd[(comp[nodes[s]] == comp[nodes[t]] ? p : 1) * 100];
3.24 + }
3.25 +}
3.26 +
3.27 +template <typename UGraph, typename CapacityMap>
3.28 +void genBikeWheelUGraph(UGraph& g, CapacityMap& c, int n) {
3.29 + std::vector<typename UGraph::Node> nodes(n);
3.30 + for (int i = 0; i < n; ++i) {
3.31 + nodes[i] = g.addNode();
3.32 + }
3.33 + for (int i = 0; i < n - 2; ++i) {
3.34 + c[g.addEdge(nodes[i], nodes[n - 1 - (i % 2)])] = 2;
3.35 + }
3.36 + for (int i = 1; i < n - 2; ++i) {
3.37 + c[g.addEdge(nodes[i - 1], nodes[i])] = n - 1;
3.38 + }
3.39 + c[g.addEdge(nodes[n - 3], nodes[0])] = n - 1;
3.40 + c[g.addEdge(nodes[n - 2], nodes[n - 1])] = 2;
3.41 +}
3.42 +
3.43 +template <typename UGraph, typename CapacityMap>
3.44 +void genRegUGraph(UGraph& g, CapacityMap& c, int n, int d) {
3.45 + std::vector<typename UGraph::Node> nodes(n);
3.46 + for (int i = 0; i < n; ++i) {
3.47 + nodes[i] = g.addNode();
3.48 + }
3.49 + for (int k = 0; k < d; ++k) {
3.50 + for (int i = 0; i < n; ++i) {
3.51 + int r = rnd[n];
3.52 + typename UGraph::Node t = nodes[r];
3.53 + nodes[r] = nodes[i];
3.54 + nodes[i] = t;
3.55 + }
3.56 + for (int i = 1; i < n; ++i) {
3.57 + c[g.addEdge(nodes[i - 1], nodes[i])] = 1;
3.58 + }
3.59 + c[g.addEdge(nodes[n - 1], nodes[0])] = 1;
3.60 + }
3.61 +}
3.62 +
3.63 +template <typename UGraph, typename CapacityMap>
3.64 +void genCdgUGraph(UGraph& g, CapacityMap& c, int n, int d) {
3.65 + std::vector<typename UGraph::Node> nodes(n);
3.66 + for (int i = 0; i < n; ++i) {
3.67 + nodes[i] = g.addNode();
3.68 + }
3.69 + std::vector<typename UGraph::Node> mix(n * d);
3.70 + for (int i = 0; i < n; ++i) {
3.71 + for (int j = 0; j < d; ++j) {
3.72 + mix[i * d + j] = nodes[i];
3.73 + }
3.74 + }
3.75 + while (mix.size() >= 2) {
3.76 + int r;
3.77 + r = rnd[mix.size()];
3.78 + typename UGraph::Node s = mix[r];
3.79 + mix[r] = mix.back(); mix.pop_back();
3.80 + r = rnd[mix.size()];
3.81 + typename UGraph::Node t = mix[r];
3.82 + mix[r] = mix.back(); mix.pop_back();
3.83 + c[g.addEdge(s, t)] = 1;
3.84 + }
3.85 +}