/* -*- C++ -*-

  * demo/simann_maxcut_demo.cc - Part of LEMON, a generic C++ optimization

  * library

  *

  * Copyright (C) 2006 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.

  *

  */

 /// \ingroup demos

 /// \file

 /// \brief A program demonstrating the simulated annealing algorithm class.

 ///

 /// This program tries to find a maximal cut in a graph using simulated

 /// annealing. It starts from a random solution and then in each step it

 /// chooses a node and moves it to the other side of the cut.

 ///

 /// \include simann_maxcut_demo.cc

 #include <iostream>

 #include <cstdlib>

 #include <lemon/simann.h>

 #include <lemon/list_graph.h>

 #include <lemon/graph_reader.h>

 using namespace lemon;

 typedef ListGraph Graph;

 typedef Graph::Node Node;

 typedef Graph::Edge Edge;

 typedef Graph::NodeIt NodeIt;

 typedef Graph::EdgeIt EdgeIt;

 typedef Graph::OutEdgeIt OutEdgeIt;

 typedef Graph::InEdgeIt InEdgeIt;

 class Entity : public EntityBase

 {

   public:

     Graph& g;

     Graph::EdgeMap<int>& w;

     Graph::NodeMap<bool> a;

     int sum;

     Node last_moved;

     Entity(Graph& _g, Graph::EdgeMap<int>& _w) : g(_g), w(_w), a(_g) {}

     double mutate() {

       static const int node_num = countNodes(g);

       int i = 1 + (int) (node_num * (rand() / (RAND_MAX + 1.0)));

       NodeIt n(g);

       int j = 1;

       while (j < i) {

         ++n;

         ++j;

       }

       for (OutEdgeIt e(g, n); e != INVALID; ++e) {

         if (a[n] != a[g.target(e)]) sum -= w[e];

         if (a[n] == a[g.target(e)]) sum += w[e];

       }

       for (InEdgeIt e(g, n); e != INVALID; ++e) {

         if (a[g.source(e)] != a[n]) sum -= w[e];

         if (a[g.source(e)] == a[n]) sum += w[e];

       }

       bool b = a[n];

       a[n] = !b;

       last_moved = n;

       return -sum;

     }

     void revert() {

       for (OutEdgeIt e(g, last_moved); e != INVALID; ++e) {

         if (a[last_moved] != a[g.target(e)]) sum -= w[e];

         if (a[last_moved] == a[g.target(e)]) sum += w[e];

       }

       for (InEdgeIt e(g, last_moved); e != INVALID; ++e) {

         if (a[g.source(e)] != a[last_moved]) sum -= w[e];

         if (a[g.source(e)] == a[last_moved]) sum += w[e];

       }

       bool b = a[last_moved];

       a[last_moved] = !b;

     }

     Entity* clone() { return new Entity(*this); }

     void randomize() {

       for (NodeIt n(g); n != INVALID; ++n)

         a[n] = false;

       for (NodeIt n(g); n != INVALID; ++n)

         if (rand() < 0.5) a[n] = true;

       sum = 0;

       for (EdgeIt e(g); e != INVALID; ++e)

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

           sum += w[e];

     }

 };

 int main()

 {

   Graph g;

   Graph::EdgeMap<int> w(g);

   GraphReader<Graph> reader("simann_maxcut_demo.lgf", g);

   reader.readEdgeMap("weight", w);

   reader.run();

   Entity e(g, w);

   SimAnn simann;

   SimpleController ctrl;

   simann.setController(ctrl);

   simann.setEntity(e);

   simann.run();

   Entity* be = (Entity *) simann.getBestEntity();

   std::cout << be->sum << std::endl;

   for (NodeIt n(g); n != INVALID; ++n)

     if (be->a[n]) std::cout << g.id(n) << ": 1" << std::endl;

     else std::cout << g.id(n) << ": 0" << std::endl;

 }