/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2007

  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

  * (Egervary Research Group on Combinatorial Optimization, EGRES).

  *

  * Permission to use, modify and distribute this software is granted

  * provided that this copyright notice appears in all copies. For

  * precise terms see the accompanying LICENSE file.

  *

  * This software is provided "AS IS" with no warranty of any kind,

  * express or implied, and with no claim as to its suitability for any

  * purpose.

  *

  */

 #include <lemon/list_graph.h>

 #include <lemon/hao_orlin.h>

 #include <lemon/nagamochi_ibaraki.h>

 #include <lemon/time_measure.h>

 using namespace lemon;

 #include "min_cut_graphs.h"

 void testRegUGraph();

 void testNoiUGraph();

 void testBikeWheelUGraph();

 int main() {

   testRegUGraph();

   testNoiUGraph();

   testBikeWheelUGraph();

   return 0;

 }

 //#define int long long

 int cutValue(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c,

            const ListUGraph::NodeMap<bool>& n) {

   int v = 0;

   for (ListUGraph::UEdgeIt e(g); e != INVALID; ++e) {

     if (n[g.source(e)] != n[g.target(e)]) {

       v += c[e];

     }

   }

   return v;

 }

 int cutSize(const ListUGraph& g, const ListUGraph::NodeMap<bool>& nm) {

   int m = 0;

   for (ListUGraph::NodeIt n(g); n != INVALID; ++n) {

     if (nm[n]) {

       ++m;

     }

   }

   return m;

 }

 int testNI(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {

   TimeReport tr("Nagamochi-Ibaraki : ");

   NagamochiIbaraki<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);

   alg.run();

   ListUGraph::NodeMap<bool> n(g);

   alg.minCut(n);

   std::cout << "Check : " << cutValue(g, c, n) << ' '

             << cutSize(g, n) << std::endl;

   return alg.minCut();

 }

 int testHO(const ListUGraph& g, const ListUGraph::UEdgeMap<int>& c) {

   TimeReport tr("Hao-Orlin : ");

   HaoOrlin<ListUGraph, ListUGraph::UEdgeMap<int> > alg(g, c);

   alg.init();

   alg.calculateOut();

   ListUGraph::NodeMap<bool> n(g);

   alg.minCut(n);

   std::cout << "Check : " << cutValue(g, c, n) << ' '

             << cutSize(g, n) << std::endl;

   return alg.minCut();

 }

 void testBikeWheelUGraph(int n) {

   ListUGraph g;

   ListUGraph::UEdgeMap<int> c(g);

   genBikeWheelUGraph(g, c, n);

   std::cout << "Node number : " << n << std::endl;

   std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;

   std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;

 }

 void testBikeWheelUGraph() {

   std::cout << "BikeWheelUGraph : " << std::endl;

   for (int k = 10; k <= 13; ++k) {

     int n = 1 << k;

     testBikeWheelUGraph(n);

   }

 }

 void testNoiUGraph(int n, int d, int k, int p) {

   ListUGraph g;

   ListUGraph::UEdgeMap<int> c(g);

   genNoiUGraph(g, c, n, d, k, p);

   std::cout << "Node number : " << n << std::endl;

   std::cout << "Density : " << d << std::endl;

   std::cout << "Tight components : " << k << std::endl;

   std::cout << "Scale : " << p << std::endl;

   std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;

   std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;

 }

 void testNoiUGraph() {

   std::cout << "NoiUGraph : " << std::endl; 

   std::cout << "Serial 1 : " << std::endl;

   for (int n = 300; n <= 1000; n += 100) {

     testNoiUGraph(n, 50, 1, n);

   }

   std::cout << "Serial 2 : " << std::endl;

   for (int n = 300; n <= 1000; n += 100) {

     testNoiUGraph(n, 50, 2, n);

   }

   std::cout << "Serial 3 : " << std::endl;

   int da3[] = { 5, 10, 25, 50, 75, 100 };

   int dn3 = sizeof(da3) / sizeof(da3[0]);

   for (int d = 0; d < dn3; ++d) {

     testNoiUGraph(1000, da3[d], 1, 1000);

   }

   std::cout << "Serial 4 : " << std::endl;

   for (int d = 0; d < dn3; ++d) {

     testNoiUGraph(1000, da3[d], 2, 1000);

   }

   std::cout << "Serial 5 : " << std::endl;

   int ka5[] = {1, 2, 3, 5, 7, 10, 20, 30, 33, 35, 

                40, 50, 100, 200, 300, 400, 500};

   int kn5 = sizeof(ka5) / sizeof(ka5[0]);

   for (int k = 0; k < kn5; ++k) {

     testNoiUGraph(1000, 50, ka5[k], 1000);

   }

   std::cout << "Serial 6 : " << std::endl;

   int pa6[] = { 5000, 2000, 1000, 500, 250, 100, 50, 10, 1};

   int pn6 = sizeof(pa6) / sizeof(pa6[0]);

   for (int p = 0; p < pn6; ++p) {

     testNoiUGraph(1000, 50, 2, pa6[p]);

   }  

 }

 void testRegUGraph(int n, int d) {

   ListUGraph g;

   ListUGraph::UEdgeMap<int> c(g);

   genRegUGraph(g, c, n, d);

   std::cout << "Node number : " << n << std::endl;

   std::cout << "Number of cycles : " << d << std::endl;

   std::cout << "Hao-Orlin : " << testHO(g, c) << std::endl;

   std::cout << "Nagamochi-Ibaraki : " << testNI(g, c) << std::endl;

 }

 void testRegUGraph() {

   std::cout << "RegUGraph : " << std::endl; 

   std::cout << "Serial 1 : " << std::endl;

   int da1[] = { 1, 3, 10, 33, 100, 333, 1000};

   int dn1 = sizeof(da1) / sizeof(da1[0]);

   for (int d = 0; d < dn1; ++d) {

     testRegUGraph(1001, da1[d]);

   }

   std::cout << "Serial 2 : " << std::endl;

   int na2[] = { 50, 100, 200, 400, 800};

   int nn2 = sizeof(na2) / sizeof(na2[0]);

   for (int n = 0; n < nn2; ++n) {

     testRegUGraph(na2[n], 50);

   }

   std::cout << "Serial 3 : " << std::endl;

   for (int n = 8; n <= 14; ++n) {

     testRegUGraph(1 << n, 2);

   }

   std::cout << "Serial 4 : " << std::endl;

   for (int n = 7; n <= 11; ++n) {

     testRegUGraph(1 << n, 1 << (n - 4));

   }  

 }