Consider the CPXMIP_OPTIMAL_TOL status as OPTIMAL too.
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #include <lemon/list_graph.h>
21 #include <lemon/hao_orlin.h>
22 #include <lemon/nagamochi_ibaraki.h>
23 #include <lemon/time_measure.h>
25 using namespace lemon;
27 #include "min_cut_graphs.h"
32 void testBikeWheelUGraph();
37 testBikeWheelUGraph();
41 //#define int long long
44 int cutValue(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c,
45 const ListUGraph::NodeMap<bool>& n) {
47 for (ListUGraph::UEdgeIt e(g); e != INVALID; ++e) {
48 if (n[g.source(e)] != n[g.target(e)]) {
55 int cutSize(const ListUGraph& g, const ListUGraph::NodeMap<bool>& nm) {
57 for (ListUGraph::NodeIt n(g); n != INVALID; ++n) {
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);
69 ListUGraph::NodeMap<bool> n(g);
71 std::cout << "Check : " << cutValue(g, c, n) << ' '
72 << cutSize(g, n) << std::endl;
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);
81 ListUGraph::NodeMap<bool> n(g);
83 std::cout << "Check : " << cutValue(g, c, n) << ' '
84 << cutSize(g, n) << std::endl;
88 void testBikeWheelUGraph(int n) {
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;
97 void testBikeWheelUGraph() {
98 std::cout << "BikeWheelUGraph : " << std::endl;
99 for (int k = 10; k <= 13; ++k) {
101 testBikeWheelUGraph(n);
105 void testNoiUGraph(int n, int d, int k, int p) {
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;
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);
124 std::cout << "Serial 2 : " << std::endl;
125 for (int n = 300; n <= 1000; n += 100) {
126 testNoiUGraph(n, 50, 2, n);
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);
134 std::cout << "Serial 4 : " << std::endl;
135 for (int d = 0; d < dn3; ++d) {
136 testNoiUGraph(1000, da3[d], 2, 1000);
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);
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]);
154 void testRegUGraph(int n, int d) {
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;
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]);
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);
178 std::cout << "Serial 3 : " << std::endl;
179 for (int n = 8; n <= 14; ++n) {
180 testRegUGraph(1 << n, 2);
182 std::cout << "Serial 4 : " << std::endl;
183 for (int n = 7; n <= 11; ++n) {
184 testRegUGraph(1 << n, 1 << (n - 4));