1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/benchmark/min_cut.cc Thu Jan 11 21:27:51 2007 +0000
1.3 @@ -0,0 +1,169 @@
1.4 +#include <lemon/list_graph.h>
1.5 +
1.6 +#include <lemon/hao_orlin.h>
1.7 +#include <lemon/nagamochi_ibaraki.h>
1.8 +#include <lemon/time_measure.h>
1.9 +
1.10 +using namespace lemon;
1.11 +
1.12 +#include "min_cut_graphs.h"
1.13 +
1.14 +
1.15 +void testRegUGraph();
1.16 +void testNoiUGraph();
1.17 +void testBikeWheelUGraph();
1.18 +
1.19 +int main() {
1.20 + testRegUGraph();
1.21 + testNoiUGraph();
1.22 + testBikeWheelUGraph();
1.23 + return 0;
1.24 +}
1.25 +
1.26 +//#define int long long
1.27 +
1.28 +
1.29 +int cutValue(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c,
1.30 + const ListUGraph::NodeMap<bool>& n) {
1.31 + int v = 0;
1.32 + for (ListUGraph::UEdgeIt e(g); e != INVALID; ++e) {
1.33 + if (n[g.source(e)] != n[g.target(e)]) {
1.34 + v += c[e];
1.35 + }
1.36 + }
1.37 + return v;
1.38 +}
1.39 +
1.40 +int cutSize(const ListUGraph& g, const ListUGraph::NodeMap<bool>& nm) {
1.41 + int m = 0;
1.42 + for (ListUGraph::NodeIt n(g); n != INVALID; ++n) {
1.43 + if (nm[n]) {
1.44 + ++m;
1.45 + }
1.46 + }
1.47 + return m;
1.48 +}
1.49 +
1.50 +int testNI(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
1.51 + TimeReport tr("Nagamochi-Ibaraki : ");
1.52 + NagamochiIbaraki<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
1.53 + alg.run();
1.54 + ListUGraph::NodeMap<bool> n(g);
1.55 + alg.minCut(n);
1.56 + std::cout << "Check : " << cutValue(g, c, n) << ' '
1.57 + << cutSize(g, n) << std::endl;
1.58 + return alg.minCut();
1.59 +}
1.60 +
1.61 +int testHO(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
1.62 + TimeReport tr("Hao-Orlin : ");
1.63 + HaoOrlin<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
1.64 + alg.init();
1.65 + alg.calculateOut();
1.66 + ListUGraph::NodeMap<bool> n(g);
1.67 + alg.minCut(n);
1.68 + std::cout << "Check : " << cutValue(g, c, n) << ' '
1.69 + << cutSize(g, n) << std::endl;
1.70 + return alg.minCut();
1.71 +}
1.72 +
1.73 +void testBikeWheelUGraph(int n) {
1.74 + ListUGraph g;
1.75 + ListUGraph::UEdgeMap<int> c(g);
1.76 + genBikeWheelUGraph(g, c, n);
1.77 + std::cout << "Node number : " << n << std::endl;
1.78 + std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
1.79 + std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
1.80 +}
1.81 +
1.82 +void testBikeWheelUGraph() {
1.83 + std::cout << "BikeWheelUGraph : " << std::endl;
1.84 + for (int k = 10; k <= 13; ++k) {
1.85 + int n = 1 << k;
1.86 + testBikeWheelUGraph(n);
1.87 + }
1.88 +}
1.89 +
1.90 +void testNoiUGraph(int n, int d, int k, int p) {
1.91 + ListUGraph g;
1.92 + ListUGraph::UEdgeMap<int> c(g);
1.93 + genNoiUGraph(g, c, n, d, k, p);
1.94 + std::cout << "Node number : " << n << std::endl;
1.95 + std::cout << "Density : " << d << std::endl;
1.96 + std::cout << "Tight components : " << k << std::endl;
1.97 + std::cout << "Scale : " << p << std::endl;
1.98 + std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
1.99 + std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
1.100 +}
1.101 +
1.102 +
1.103 +void testNoiUGraph() {
1.104 + std::cout << "NoiUGraph : " << std::endl;
1.105 + std::cout << "Serial 1 : " << std::endl;
1.106 + for (int n = 300; n <= 1000; n += 100) {
1.107 + testNoiUGraph(n, 50, 1, n);
1.108 + }
1.109 + std::cout << "Serial 2 : " << std::endl;
1.110 + for (int n = 300; n <= 1000; n += 100) {
1.111 + testNoiUGraph(n, 50, 2, n);
1.112 + }
1.113 + std::cout << "Serial 3 : " << std::endl;
1.114 + int da3[] = { 5, 10, 25, 50, 75, 100 };
1.115 + int dn3 = sizeof(da3) / sizeof(da3[0]);
1.116 + for (int d = 0; d < dn3; ++d) {
1.117 + testNoiUGraph(1000, da3[d], 1, 1000);
1.118 + }
1.119 + std::cout << "Serial 4 : " << std::endl;
1.120 + for (int d = 0; d < dn3; ++d) {
1.121 + testNoiUGraph(1000, da3[d], 2, 1000);
1.122 + }
1.123 + std::cout << "Serial 5 : " << std::endl;
1.124 + int ka5[] = {1, 2, 3, 5, 7, 10, 20, 30, 33, 35,
1.125 + 40, 50, 100, 200, 300, 400, 500};
1.126 + int kn5 = sizeof(ka5) / sizeof(ka5[0]);
1.127 + for (int k = 0; k < kn5; ++k) {
1.128 + testNoiUGraph(1000, 50, ka5[k], 1000);
1.129 + }
1.130 + std::cout << "Serial 6 : " << std::endl;
1.131 + int pa6[] = { 5000, 2000, 1000, 500, 250, 100, 50, 10, 1};
1.132 + int pn6 = sizeof(pa6) / sizeof(pa6[0]);
1.133 + for (int p = 0; p < pn6; ++p) {
1.134 + testNoiUGraph(1000, 50, 2, pa6[p]);
1.135 + }
1.136 +
1.137 +}
1.138 +
1.139 +void testRegUGraph(int n, int d) {
1.140 + ListUGraph g;
1.141 + ListUGraph::UEdgeMap<int> c(g);
1.142 + genRegUGraph(g, c, n, d);
1.143 + std::cout << "Node number : " << n << std::endl;
1.144 + std::cout << "Number of cycles : " << d << std::endl;
1.145 + std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
1.146 + std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
1.147 +}
1.148 +
1.149 +void testRegUGraph() {
1.150 + std::cout << "RegUGraph : " << std::endl;
1.151 + std::cout << "Serial 1 : " << std::endl;
1.152 + int da1[] = { 1, 3, 10, 33, 100, 333, 1000};
1.153 + int dn1 = sizeof(da1) / sizeof(da1[0]);
1.154 + for (int d = 0; d < dn1; ++d) {
1.155 + testRegUGraph(1001, da1[d]);
1.156 + }
1.157 + std::cout << "Serial 2 : " << std::endl;
1.158 + int na2[] = { 50, 100, 200, 400, 800};
1.159 + int nn2 = sizeof(na2) / sizeof(na2[0]);
1.160 + for (int n = 0; n < nn2; ++n) {
1.161 + testRegUGraph(na2[n], 50);
1.162 + }
1.163 + std::cout << "Serial 3 : " << std::endl;
1.164 + for (int n = 8; n <= 14; ++n) {
1.165 + testRegUGraph(1 << n, 2);
1.166 + }
1.167 + std::cout << "Serial 4 : " << std::endl;
1.168 + for (int n = 7; n <= 11; ++n) {
1.169 + testRegUGraph(1 << n, 1 << (n - 4));
1.170 + }
1.171 +}
1.172 +