COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/min_cut.cc @ 2341:46a6311ceffa

Last change on this file since 2341:46a6311ceffa was 2341:46a6311ceffa, checked in by Balazs Dezso, 13 years ago

Undirected minimum cut benchmarking

File size: 4.6 KB
Line 
1#include <lemon/list_graph.h>
2
3#include <lemon/hao_orlin.h>
4#include <lemon/nagamochi_ibaraki.h>
5#include <lemon/time_measure.h>
6
7using namespace lemon;
8
9#include "min_cut_graphs.h"
10
11
12void testRegUGraph();
13void testNoiUGraph();
14void testBikeWheelUGraph();
15
16int main() {
17  testRegUGraph();
18  testNoiUGraph();
19  testBikeWheelUGraph();
20  return 0;
21}
22
23//#define int long long
24
25
26int cutValue(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c,
27           const ListUGraph::NodeMap<bool>& n) {
28  int v = 0;
29  for (ListUGraph::UEdgeIt e(g); e != INVALID; ++e) {
30    if (n[g.source(e)] != n[g.target(e)]) {
31      v += c[e];
32    }
33  }
34  return v;
35}
36
37int cutSize(const ListUGraph& g, const ListUGraph::NodeMap<bool>& nm) {
38  int m = 0;
39  for (ListUGraph::NodeIt n(g); n != INVALID; ++n) {
40    if (nm[n]) {
41      ++m;
42    }
43  }
44  return m;
45}
46
47int testNI(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
48  TimeReport tr("Nagamochi-Ibaraki : ");
49  NagamochiIbaraki<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
50  alg.run();
51  ListUGraph::NodeMap<bool> n(g);
52  alg.minCut(n);
53  std::cout << "Check : " << cutValue(g, c, n) << ' '
54            << cutSize(g, n) << std::endl;
55  return alg.minCut();
56}
57
58int testHO(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
59  TimeReport tr("Hao-Orlin : ");
60  HaoOrlin<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
61  alg.init();
62  alg.calculateOut();
63  ListUGraph::NodeMap<bool> n(g);
64  alg.minCut(n);
65  std::cout << "Check : " << cutValue(g, c, n) << ' '
66            << cutSize(g, n) << std::endl;
67  return alg.minCut();
68}
69
70void testBikeWheelUGraph(int n) {
71  ListUGraph g;
72  ListUGraph::UEdgeMap<int> c(g);
73  genBikeWheelUGraph(g, c, n);
74  std::cout << "Node number : " << n << std::endl;
75  std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
76  std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
77}
78
79void testBikeWheelUGraph() {
80  std::cout << "BikeWheelUGraph : " << std::endl;
81  for (int k = 10; k <= 13; ++k) {
82    int n = 1 << k;
83    testBikeWheelUGraph(n);
84  }
85}
86
87void testNoiUGraph(int n, int d, int k, int p) {
88  ListUGraph g;
89  ListUGraph::UEdgeMap<int> c(g);
90  genNoiUGraph(g, c, n, d, k, p);
91  std::cout << "Node number : " << n << std::endl;
92  std::cout << "Density : " << d << std::endl;
93  std::cout << "Tight components : " << k << std::endl;
94  std::cout << "Scale : " << p << std::endl;
95  std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
96  std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
97}
98
99
100void testNoiUGraph() {
101  std::cout << "NoiUGraph : " << std::endl;
102  std::cout << "Serial 1 : " << std::endl;
103  for (int n = 300; n <= 1000; n += 100) {
104    testNoiUGraph(n, 50, 1, n);
105  }
106  std::cout << "Serial 2 : " << std::endl;
107  for (int n = 300; n <= 1000; n += 100) {
108    testNoiUGraph(n, 50, 2, n);
109  }
110  std::cout << "Serial 3 : " << std::endl;
111  int da3[] = { 5, 10, 25, 50, 75, 100 };
112  int dn3 = sizeof(da3) / sizeof(da3[0]);
113  for (int d = 0; d < dn3; ++d) {
114    testNoiUGraph(1000, da3[d], 1, 1000);
115  }
116  std::cout << "Serial 4 : " << std::endl;
117  for (int d = 0; d < dn3; ++d) {
118    testNoiUGraph(1000, da3[d], 2, 1000);
119  }
120  std::cout << "Serial 5 : " << std::endl;
121  int ka5[] = {1, 2, 3, 5, 7, 10, 20, 30, 33, 35,
122               40, 50, 100, 200, 300, 400, 500};
123  int kn5 = sizeof(ka5) / sizeof(ka5[0]);
124  for (int k = 0; k < kn5; ++k) {
125    testNoiUGraph(1000, 50, ka5[k], 1000);
126  }
127  std::cout << "Serial 6 : " << std::endl;
128  int pa6[] = { 5000, 2000, 1000, 500, 250, 100, 50, 10, 1};
129  int pn6 = sizeof(pa6) / sizeof(pa6[0]);
130  for (int p = 0; p < pn6; ++p) {
131    testNoiUGraph(1000, 50, 2, pa6[p]);
132  } 
133 
134}
135
136void testRegUGraph(int n, int d) {
137  ListUGraph g;
138  ListUGraph::UEdgeMap<int> c(g);
139  genRegUGraph(g, c, n, d);
140  std::cout << "Node number : " << n << std::endl;
141  std::cout << "Number of cycles : " << d << std::endl;
142  std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
143  std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
144}
145
146void testRegUGraph() {
147  std::cout << "RegUGraph : " << std::endl;
148  std::cout << "Serial 1 : " << std::endl;
149  int da1[] = { 1, 3, 10, 33, 100, 333, 1000};
150  int dn1 = sizeof(da1) / sizeof(da1[0]);
151  for (int d = 0; d < dn1; ++d) {
152    testRegUGraph(1001, da1[d]);
153  }
154  std::cout << "Serial 2 : " << std::endl;
155  int na2[] = { 50, 100, 200, 400, 800};
156  int nn2 = sizeof(na2) / sizeof(na2[0]);
157  for (int n = 0; n < nn2; ++n) {
158    testRegUGraph(na2[n], 50);
159  }
160  std::cout << "Serial 3 : " << std::endl;
161  for (int n = 8; n <= 14; ++n) {
162    testRegUGraph(1 << n, 2);
163  }
164  std::cout << "Serial 4 : " << std::endl;
165  for (int n = 7; n <= 11; ++n) {
166    testRegUGraph(1 << n, 1 << (n - 4));
167  } 
168}
169
Note: See TracBrowser for help on using the repository browser.