ladanyi@1919: /* -*- C++ -*-
ladanyi@1919:  * demo/simann_maxcut_demo.cc - Part of LEMON, a generic C++ optimization
ladanyi@1919:  * library
ladanyi@1919:  *
ladanyi@1919:  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
ladanyi@1919:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
ladanyi@1919:  *
ladanyi@1919:  * Permission to use, modify and distribute this software is granted
ladanyi@1919:  * provided that this copyright notice appears in all copies. For
ladanyi@1919:  * precise terms see the accompanying LICENSE file.
ladanyi@1919:  *
ladanyi@1919:  * This software is provided "AS IS" with no warranty of any kind,
ladanyi@1919:  * express or implied, and with no claim as to its suitability for any
ladanyi@1919:  * purpose.
ladanyi@1919:  *
ladanyi@1919:  */
ladanyi@1919: 
ladanyi@1919: /// \ingroup demos
ladanyi@1919: /// \file
ladanyi@1919: /// \brief A program demonstrating the simulated annealing algorithm class.
ladanyi@1919: ///
ladanyi@1919: /// This program tries to find a maximal cut in a graph using simulated
ladanyi@1919: /// annealing. It starts from a random solution and then in each step it
ladanyi@1919: /// chooses a node and moves it to the other side of the cut.
ladanyi@1919: ///
ladanyi@1919: /// \include simann_maxcut_demo.cc
ladanyi@1919: 
ladanyi@1919: #include <iostream>
ladanyi@1919: #include <cstdlib>
ladanyi@1919: 
ladanyi@1919: #include <lemon/simann.h>
ladanyi@1919: #include <lemon/list_graph.h>
ladanyi@1919: #include <lemon/graph_reader.h>
ladanyi@1919: 
ladanyi@1919: using namespace lemon;
ladanyi@1919: 
ladanyi@1919: typedef ListGraph Graph;
ladanyi@1919: typedef Graph::Node Node;
ladanyi@1919: typedef Graph::Edge Edge;
ladanyi@1919: typedef Graph::NodeIt NodeIt;
ladanyi@1919: typedef Graph::EdgeIt EdgeIt;
ladanyi@1919: typedef Graph::OutEdgeIt OutEdgeIt;
ladanyi@1919: typedef Graph::InEdgeIt InEdgeIt;
ladanyi@1919: 
ladanyi@1919: class Entity : public EntityBase
ladanyi@1919: {
ladanyi@1919:   public:
ladanyi@1919:     Graph& g;
ladanyi@1919:     Graph::EdgeMap<int>& w;
ladanyi@1919:     Graph::NodeMap<bool> a;
ladanyi@1919:     int sum;
ladanyi@1919:     Node last_moved;
ladanyi@1919:     Entity(Graph& _g, Graph::EdgeMap<int>& _w) : g(_g), w(_w), a(_g) {}
ladanyi@1919:     double mutate() {
ladanyi@1919:       static const int node_num = countNodes(g);
ladanyi@1919:       int i = 1 + (int) (node_num * (rand() / (RAND_MAX + 1.0)));
ladanyi@1919:       NodeIt n(g);
ladanyi@1919:       int j = 1;
ladanyi@1919:       while (j < i) {
ladanyi@1919:         ++n;
ladanyi@1919:         ++j;
ladanyi@1919:       }
ladanyi@1919:       for (OutEdgeIt e(g, n); e != INVALID; ++e) {
ladanyi@1919:         if (a[n] != a[g.target(e)]) sum -= w[e];
ladanyi@1919:         if (a[n] == a[g.target(e)]) sum += w[e];
ladanyi@1919:       }
ladanyi@1919:       for (InEdgeIt e(g, n); e != INVALID; ++e) {
ladanyi@1919:         if (a[g.source(e)] != a[n]) sum -= w[e];
ladanyi@1919:         if (a[g.source(e)] == a[n]) sum += w[e];
ladanyi@1919:       }
ladanyi@1919:       bool b = a[n];
ladanyi@1919:       a[n] = !b;
ladanyi@1919:       last_moved = n;
ladanyi@1919:       return -sum;
ladanyi@1919:     }
ladanyi@1919:     void revert() {
ladanyi@1919:       for (OutEdgeIt e(g, last_moved); e != INVALID; ++e) {
ladanyi@1919:         if (a[last_moved] != a[g.target(e)]) sum -= w[e];
ladanyi@1919:         if (a[last_moved] == a[g.target(e)]) sum += w[e];
ladanyi@1919:       }
ladanyi@1919:       for (InEdgeIt e(g, last_moved); e != INVALID; ++e) {
ladanyi@1919:         if (a[g.source(e)] != a[last_moved]) sum -= w[e];
ladanyi@1919:         if (a[g.source(e)] == a[last_moved]) sum += w[e];
ladanyi@1919:       }
ladanyi@1919:       bool b = a[last_moved];
ladanyi@1919:       a[last_moved] = !b;
ladanyi@1919:     }
ladanyi@1919:     Entity* clone() { return new Entity(*this); }
ladanyi@1919:     void randomize() {
ladanyi@1919:       for (NodeIt n(g); n != INVALID; ++n)
ladanyi@1919:         a[n] = false;
ladanyi@1919:       for (NodeIt n(g); n != INVALID; ++n)
ladanyi@1919:         if (rand() < 0.5) a[n] = true;
ladanyi@1919:       sum = 0;
ladanyi@1919:       for (EdgeIt e(g); e != INVALID; ++e)
ladanyi@1919:         if (a[g.source(e)] != a[g.target(e)])
ladanyi@1919:           sum += w[e];
ladanyi@1919:     }
ladanyi@1919: };
ladanyi@1919: 
ladanyi@1919: int main()
ladanyi@1919: {
ladanyi@1919:   Graph g;
ladanyi@1919:   Graph::EdgeMap<int> w(g);
ladanyi@1919: 
ladanyi@1919:   GraphReader<Graph> reader("simann_maxcut_demo.lgf", g);
ladanyi@1919:   reader.readEdgeMap("weight", w);
ladanyi@1919:   reader.run();
ladanyi@1919: 
ladanyi@1919:   Entity e(g, w);
ladanyi@1919: 
ladanyi@1919:   SimAnn simann;
ladanyi@1919:   SimpleController ctrl;
ladanyi@1919:   simann.setController(ctrl);
ladanyi@1919:   simann.setEntity(e);
ladanyi@1919:   simann.run();
ladanyi@1919:   
ladanyi@1919:   Entity* be = (Entity *) simann.getBestEntity();
ladanyi@1919:   std::cout << be->sum << std::endl;
ladanyi@1919:   for (NodeIt n(g); n != INVALID; ++n)
ladanyi@1919:     if (be->a[n]) std::cout << g.id(n) << ": 1" << std::endl;
ladanyi@1919:     else std::cout << g.id(n) << ": 0" << std::endl;
ladanyi@1919: }