simann_maxcut_demo.cc File Reference

---

Detailed Description

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.

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2008
 * 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 <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 + rnd[node_num];
      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 (rnd.boolean(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 = static_cast<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;
}

#include <iostream>
#include <cstdlib>
#include <lemon/simann.h>
#include <lemon/list_graph.h>
#include <lemon/graph_reader.h>