alpar@2391: /* -*- C++ -*- alpar@2391: * alpar@2391: * This file is a part of LEMON, a generic C++ optimization library alpar@2391: * alpar@2553: * Copyright (C) 2003-2008 alpar@2391: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport alpar@2391: * (Egervary Research Group on Combinatorial Optimization, EGRES). alpar@2391: * alpar@2391: * Permission to use, modify and distribute this software is granted alpar@2391: * provided that this copyright notice appears in all copies. For alpar@2391: * precise terms see the accompanying LICENSE file. alpar@2391: * alpar@2391: * This software is provided "AS IS" with no warranty of any kind, alpar@2391: * express or implied, and with no claim as to its suitability for any alpar@2391: * purpose. alpar@2391: * alpar@2391: */ alpar@2391: deba@2341: #include deba@2341: deba@2341: #include deba@2341: #include deba@2341: #include deba@2341: deba@2341: using namespace lemon; deba@2341: deba@2341: #include "min_cut_graphs.h" deba@2341: deba@2341: deba@2341: void testRegUGraph(); deba@2341: void testNoiUGraph(); deba@2341: void testBikeWheelUGraph(); deba@2341: deba@2341: int main() { deba@2341: testRegUGraph(); deba@2341: testNoiUGraph(); deba@2341: testBikeWheelUGraph(); deba@2341: return 0; deba@2341: } deba@2341: deba@2341: //#define int long long deba@2341: deba@2341: deba@2341: int cutValue(const ListUGraph& g, const ListUGraph::UEdgeMap& c, deba@2341: const ListUGraph::NodeMap& n) { deba@2341: int v = 0; deba@2341: for (ListUGraph::UEdgeIt e(g); e != INVALID; ++e) { deba@2341: if (n[g.source(e)] != n[g.target(e)]) { deba@2341: v += c[e]; deba@2341: } deba@2341: } deba@2341: return v; deba@2341: } deba@2341: deba@2341: int cutSize(const ListUGraph& g, const ListUGraph::NodeMap& nm) { deba@2341: int m = 0; deba@2341: for (ListUGraph::NodeIt n(g); n != INVALID; ++n) { deba@2341: if (nm[n]) { deba@2341: ++m; deba@2341: } deba@2341: } deba@2341: return m; deba@2341: } deba@2341: deba@2341: int testNI(const ListUGraph& g, const ListUGraph::UEdgeMap& c) { deba@2341: TimeReport tr("Nagamochi-Ibaraki : "); deba@2341: NagamochiIbaraki > alg(g, c); deba@2341: alg.run(); deba@2341: ListUGraph::NodeMap n(g); deba@2341: alg.minCut(n); deba@2341: std::cout << "Check : " << cutValue(g, c, n) << ' ' deba@2341: << cutSize(g, n) << std::endl; deba@2341: return alg.minCut(); deba@2341: } deba@2341: deba@2341: int testHO(const ListUGraph& g, const ListUGraph::UEdgeMap& c) { deba@2341: TimeReport tr("Hao-Orlin : "); deba@2341: HaoOrlin > alg(g, c); deba@2341: alg.init(); deba@2341: alg.calculateOut(); deba@2341: ListUGraph::NodeMap n(g); deba@2341: alg.minCut(n); deba@2341: std::cout << "Check : " << cutValue(g, c, n) << ' ' deba@2341: << cutSize(g, n) << std::endl; deba@2341: return alg.minCut(); deba@2341: } deba@2341: deba@2341: void testBikeWheelUGraph(int n) { deba@2341: ListUGraph g; deba@2341: ListUGraph::UEdgeMap c(g); deba@2341: genBikeWheelUGraph(g, c, n); deba@2341: std::cout << "Node number : " << n << std::endl; deba@2341: std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl; deba@2341: std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl; deba@2341: } deba@2341: deba@2341: void testBikeWheelUGraph() { deba@2341: std::cout << "BikeWheelUGraph : " << std::endl; deba@2341: for (int k = 10; k <= 13; ++k) { deba@2341: int n = 1 << k; deba@2341: testBikeWheelUGraph(n); deba@2341: } deba@2341: } deba@2341: deba@2341: void testNoiUGraph(int n, int d, int k, int p) { deba@2341: ListUGraph g; deba@2341: ListUGraph::UEdgeMap c(g); deba@2341: genNoiUGraph(g, c, n, d, k, p); deba@2341: std::cout << "Node number : " << n << std::endl; deba@2341: std::cout << "Density : " << d << std::endl; deba@2341: std::cout << "Tight components : " << k << std::endl; deba@2341: std::cout << "Scale : " << p << std::endl; deba@2341: std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl; deba@2341: std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl; deba@2341: } deba@2341: deba@2341: deba@2341: void testNoiUGraph() { deba@2341: std::cout << "NoiUGraph : " << std::endl; deba@2341: std::cout << "Serial 1 : " << std::endl; deba@2341: for (int n = 300; n <= 1000; n += 100) { deba@2341: testNoiUGraph(n, 50, 1, n); deba@2341: } deba@2341: std::cout << "Serial 2 : " << std::endl; deba@2341: for (int n = 300; n <= 1000; n += 100) { deba@2341: testNoiUGraph(n, 50, 2, n); deba@2341: } deba@2341: std::cout << "Serial 3 : " << std::endl; deba@2341: int da3[] = { 5, 10, 25, 50, 75, 100 }; deba@2341: int dn3 = sizeof(da3) / sizeof(da3[0]); deba@2341: for (int d = 0; d < dn3; ++d) { deba@2341: testNoiUGraph(1000, da3[d], 1, 1000); deba@2341: } deba@2341: std::cout << "Serial 4 : " << std::endl; deba@2341: for (int d = 0; d < dn3; ++d) { deba@2341: testNoiUGraph(1000, da3[d], 2, 1000); deba@2341: } deba@2341: std::cout << "Serial 5 : " << std::endl; deba@2341: int ka5[] = {1, 2, 3, 5, 7, 10, 20, 30, 33, 35, deba@2341: 40, 50, 100, 200, 300, 400, 500}; deba@2341: int kn5 = sizeof(ka5) / sizeof(ka5[0]); deba@2341: for (int k = 0; k < kn5; ++k) { deba@2341: testNoiUGraph(1000, 50, ka5[k], 1000); deba@2341: } deba@2341: std::cout << "Serial 6 : " << std::endl; deba@2341: int pa6[] = { 5000, 2000, 1000, 500, 250, 100, 50, 10, 1}; deba@2341: int pn6 = sizeof(pa6) / sizeof(pa6[0]); deba@2341: for (int p = 0; p < pn6; ++p) { deba@2341: testNoiUGraph(1000, 50, 2, pa6[p]); deba@2341: } deba@2341: deba@2341: } deba@2341: deba@2341: void testRegUGraph(int n, int d) { deba@2341: ListUGraph g; deba@2341: ListUGraph::UEdgeMap c(g); deba@2341: genRegUGraph(g, c, n, d); deba@2341: std::cout << "Node number : " << n << std::endl; deba@2341: std::cout << "Number of cycles : " << d << std::endl; deba@2341: std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl; deba@2341: std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl; deba@2341: } deba@2341: deba@2341: void testRegUGraph() { deba@2341: std::cout << "RegUGraph : " << std::endl; deba@2341: std::cout << "Serial 1 : " << std::endl; deba@2341: int da1[] = { 1, 3, 10, 33, 100, 333, 1000}; deba@2341: int dn1 = sizeof(da1) / sizeof(da1[0]); deba@2341: for (int d = 0; d < dn1; ++d) { deba@2341: testRegUGraph(1001, da1[d]); deba@2341: } deba@2341: std::cout << "Serial 2 : " << std::endl; deba@2341: int na2[] = { 50, 100, 200, 400, 800}; deba@2341: int nn2 = sizeof(na2) / sizeof(na2[0]); deba@2341: for (int n = 0; n < nn2; ++n) { deba@2341: testRegUGraph(na2[n], 50); deba@2341: } deba@2341: std::cout << "Serial 3 : " << std::endl; deba@2341: for (int n = 8; n <= 14; ++n) { deba@2341: testRegUGraph(1 << n, 2); deba@2341: } deba@2341: std::cout << "Serial 4 : " << std::endl; deba@2341: for (int n = 7; n <= 11; ++n) { deba@2341: testRegUGraph(1 << n, 1 << (n - 4)); deba@2341: } deba@2341: } deba@2341: