COIN-OR::LEMON - Graph Library

source: lemon-0.x/benchmark/min_cut.cc

Last change on this file was 2553:bfced05fa852, checked in by Alpar Juttner, 16 years ago

Happy New Year to LEMON (+ better update-copyright-header script)

File size: 5.2 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#include <lemon/list_graph.h>
20
21#include <lemon/hao_orlin.h>
22#include <lemon/nagamochi_ibaraki.h>
23#include <lemon/time_measure.h>
24
25using namespace lemon;
26
27#include "min_cut_graphs.h"
28
29
30void testRegUGraph();
31void testNoiUGraph();
32void testBikeWheelUGraph();
33
34int main() {
35  testRegUGraph();
36  testNoiUGraph();
37  testBikeWheelUGraph();
38  return 0;
39}
40
41//#define int long long
42
43
44int cutValue(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c,
45           const ListUGraph::NodeMap<bool>& n) {
46  int v = 0;
47  for (ListUGraph::UEdgeIt e(g); e != INVALID; ++e) {
48    if (n[g.source(e)] != n[g.target(e)]) {
49      v += c[e];
50    }
51  }
52  return v;
53}
54
55int cutSize(const ListUGraph& g, const ListUGraph::NodeMap<bool>& nm) {
56  int m = 0;
57  for (ListUGraph::NodeIt n(g); n != INVALID; ++n) {
58    if (nm[n]) {
59      ++m;
60    }
61  }
62  return m;
63}
64
65int testNI(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
66  TimeReport tr("Nagamochi-Ibaraki : ");
67  NagamochiIbaraki<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
68  alg.run();
69  ListUGraph::NodeMap<bool> n(g);
70  alg.minCut(n);
71  std::cout << "Check : " << cutValue(g, c, n) << ' '
72            << cutSize(g, n) << std::endl;
73  return alg.minCut();
74}
75
76int testHO(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {
77  TimeReport tr("Hao-Orlin : ");
78  HaoOrlin<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);
79  alg.init();
80  alg.calculateOut();
81  ListUGraph::NodeMap<bool> n(g);
82  alg.minCut(n);
83  std::cout << "Check : " << cutValue(g, c, n) << ' '
84            << cutSize(g, n) << std::endl;
85  return alg.minCut();
86}
87
88void testBikeWheelUGraph(int n) {
89  ListUGraph g;
90  ListUGraph::UEdgeMap<int> c(g);
91  genBikeWheelUGraph(g, c, n);
92  std::cout << "Node number : " << n << std::endl;
93  std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
94  std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
95}
96
97void testBikeWheelUGraph() {
98  std::cout << "BikeWheelUGraph : " << std::endl;
99  for (int k = 10; k <= 13; ++k) {
100    int n = 1 << k;
101    testBikeWheelUGraph(n);
102  }
103}
104
105void testNoiUGraph(int n, int d, int k, int p) {
106  ListUGraph g;
107  ListUGraph::UEdgeMap<int> c(g);
108  genNoiUGraph(g, c, n, d, k, p);
109  std::cout << "Node number : " << n << std::endl;
110  std::cout << "Density : " << d << std::endl;
111  std::cout << "Tight components : " << k << std::endl;
112  std::cout << "Scale : " << p << std::endl;
113  std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
114  std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
115}
116
117
118void testNoiUGraph() {
119  std::cout << "NoiUGraph : " << std::endl;
120  std::cout << "Serial 1 : " << std::endl;
121  for (int n = 300; n <= 1000; n += 100) {
122    testNoiUGraph(n, 50, 1, n);
123  }
124  std::cout << "Serial 2 : " << std::endl;
125  for (int n = 300; n <= 1000; n += 100) {
126    testNoiUGraph(n, 50, 2, n);
127  }
128  std::cout << "Serial 3 : " << std::endl;
129  int da3[] = { 5, 10, 25, 50, 75, 100 };
130  int dn3 = sizeof(da3) / sizeof(da3[0]);
131  for (int d = 0; d < dn3; ++d) {
132    testNoiUGraph(1000, da3[d], 1, 1000);
133  }
134  std::cout << "Serial 4 : " << std::endl;
135  for (int d = 0; d < dn3; ++d) {
136    testNoiUGraph(1000, da3[d], 2, 1000);
137  }
138  std::cout << "Serial 5 : " << std::endl;
139  int ka5[] = {1, 2, 3, 5, 7, 10, 20, 30, 33, 35,
140               40, 50, 100, 200, 300, 400, 500};
141  int kn5 = sizeof(ka5) / sizeof(ka5[0]);
142  for (int k = 0; k < kn5; ++k) {
143    testNoiUGraph(1000, 50, ka5[k], 1000);
144  }
145  std::cout << "Serial 6 : " << std::endl;
146  int pa6[] = { 5000, 2000, 1000, 500, 250, 100, 50, 10, 1};
147  int pn6 = sizeof(pa6) / sizeof(pa6[0]);
148  for (int p = 0; p < pn6; ++p) {
149    testNoiUGraph(1000, 50, 2, pa6[p]);
150  } 
151 
152}
153
154void testRegUGraph(int n, int d) {
155  ListUGraph g;
156  ListUGraph::UEdgeMap<int> c(g);
157  genRegUGraph(g, c, n, d);
158  std::cout << "Node number : " << n << std::endl;
159  std::cout << "Number of cycles : " << d << std::endl;
160  std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;
161  std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;
162}
163
164void testRegUGraph() {
165  std::cout << "RegUGraph : " << std::endl;
166  std::cout << "Serial 1 : " << std::endl;
167  int da1[] = { 1, 3, 10, 33, 100, 333, 1000};
168  int dn1 = sizeof(da1) / sizeof(da1[0]);
169  for (int d = 0; d < dn1; ++d) {
170    testRegUGraph(1001, da1[d]);
171  }
172  std::cout << "Serial 2 : " << std::endl;
173  int na2[] = { 50, 100, 200, 400, 800};
174  int nn2 = sizeof(na2) / sizeof(na2[0]);
175  for (int n = 0; n < nn2; ++n) {
176    testRegUGraph(na2[n], 50);
177  }
178  std::cout << "Serial 3 : " << std::endl;
179  for (int n = 8; n <= 14; ++n) {
180    testRegUGraph(1 << n, 2);
181  }
182  std::cout << "Serial 4 : " << std::endl;
183  for (int n = 7; n <= 11; ++n) {
184    testRegUGraph(1 << n, 1 << (n - 4));
185  } 
186}
187
Note: See TracBrowser for help on using the repository browser.