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 | |
---|
25 | using namespace lemon; |
---|
26 | |
---|
27 | #include "min_cut_graphs.h" |
---|
28 | |
---|
29 | |
---|
30 | void testRegUGraph(); |
---|
31 | void testNoiUGraph(); |
---|
32 | void testBikeWheelUGraph(); |
---|
33 | |
---|
34 | int main() { |
---|
35 | testRegUGraph(); |
---|
36 | testNoiUGraph(); |
---|
37 | testBikeWheelUGraph(); |
---|
38 | return 0; |
---|
39 | } |
---|
40 | |
---|
41 | //#define int long long |
---|
42 | |
---|
43 | |
---|
44 | int 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 | |
---|
55 | int 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 | |
---|
65 | int 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 | |
---|
76 | int 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 | |
---|
88 | void 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 | |
---|
97 | void 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 | |
---|
105 | void 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 | |
---|
118 | void 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 | |
---|
154 | void 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 | |
---|
164 | void 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 | |
---|