/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-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;

}