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 | |
---|
7 | using namespace lemon; |
---|
8 | |
---|
9 | #include "min_cut_graphs.h" |
---|
10 | |
---|
11 | |
---|
12 | void testRegUGraph(); |
---|
13 | void testNoiUGraph(); |
---|
14 | void testBikeWheelUGraph(); |
---|
15 | |
---|
16 | int main() { |
---|
17 | testRegUGraph(); |
---|
18 | testNoiUGraph(); |
---|
19 | testBikeWheelUGraph(); |
---|
20 | return 0; |
---|
21 | } |
---|
22 | |
---|
23 | //#define int long long |
---|
24 | |
---|
25 | |
---|
26 | int 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 | |
---|
37 | int 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 | |
---|
47 | int 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 | |
---|
58 | int 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 | |
---|
70 | void 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 | |
---|
79 | void 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 | |
---|
87 | void 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 | |
---|
100 | void 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 | |
---|
136 | void 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 | |
---|
146 | void 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 | |
---|