[2341] | 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 | |
---|