source: lemon-0.x/demo/simann_maxcut_demo.cc @ 2139:582c8c28aa01

/* -*- 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;
}