demo/simann_maxcut_demo.cc
author alpar
Wed, 01 Feb 2006 11:33:16 +0000
changeset 1937 7a7a1f95cc24
child 1956 a055123339d5
permissions -rw-r--r--
Some useful scripts:
check-compiler: test whether the repo compiles warningless
with various compilers.
check-integrity: checks whether everything is svn-added,
the makefiles are correct etc.
release: creates a version numbered release. Is modifies the repository.
DO NOT PLAY WITH IT!
     1 /* -*- C++ -*-
     2  * demo/simann_maxcut_demo.cc - Part of LEMON, a generic C++ optimization
     3  * library
     4  *
     5  * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     6  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     7  *
     8  * Permission to use, modify and distribute this software is granted
     9  * provided that this copyright notice appears in all copies. For
    10  * precise terms see the accompanying LICENSE file.
    11  *
    12  * This software is provided "AS IS" with no warranty of any kind,
    13  * express or implied, and with no claim as to its suitability for any
    14  * purpose.
    15  *
    16  */
    17 
    18 /// \ingroup demos
    19 /// \file
    20 /// \brief A program demonstrating the simulated annealing algorithm class.
    21 ///
    22 /// This program tries to find a maximal cut in a graph using simulated
    23 /// annealing. It starts from a random solution and then in each step it
    24 /// chooses a node and moves it to the other side of the cut.
    25 ///
    26 /// \include simann_maxcut_demo.cc
    27 
    28 #include <iostream>
    29 #include <cstdlib>
    30 
    31 #include <lemon/simann.h>
    32 #include <lemon/list_graph.h>
    33 #include <lemon/graph_reader.h>
    34 
    35 using namespace lemon;
    36 
    37 typedef ListGraph Graph;
    38 typedef Graph::Node Node;
    39 typedef Graph::Edge Edge;
    40 typedef Graph::NodeIt NodeIt;
    41 typedef Graph::EdgeIt EdgeIt;
    42 typedef Graph::OutEdgeIt OutEdgeIt;
    43 typedef Graph::InEdgeIt InEdgeIt;
    44 
    45 class Entity : public EntityBase
    46 {
    47   public:
    48     Graph& g;
    49     Graph::EdgeMap<int>& w;
    50     Graph::NodeMap<bool> a;
    51     int sum;
    52     Node last_moved;
    53     Entity(Graph& _g, Graph::EdgeMap<int>& _w) : g(_g), w(_w), a(_g) {}
    54     double mutate() {
    55       static const int node_num = countNodes(g);
    56       int i = 1 + (int) (node_num * (rand() / (RAND_MAX + 1.0)));
    57       NodeIt n(g);
    58       int j = 1;
    59       while (j < i) {
    60         ++n;
    61         ++j;
    62       }
    63       for (OutEdgeIt e(g, n); e != INVALID; ++e) {
    64         if (a[n] != a[g.target(e)]) sum -= w[e];
    65         if (a[n] == a[g.target(e)]) sum += w[e];
    66       }
    67       for (InEdgeIt e(g, n); e != INVALID; ++e) {
    68         if (a[g.source(e)] != a[n]) sum -= w[e];
    69         if (a[g.source(e)] == a[n]) sum += w[e];
    70       }
    71       bool b = a[n];
    72       a[n] = !b;
    73       last_moved = n;
    74       return -sum;
    75     }
    76     void revert() {
    77       for (OutEdgeIt e(g, last_moved); e != INVALID; ++e) {
    78         if (a[last_moved] != a[g.target(e)]) sum -= w[e];
    79         if (a[last_moved] == a[g.target(e)]) sum += w[e];
    80       }
    81       for (InEdgeIt e(g, last_moved); e != INVALID; ++e) {
    82         if (a[g.source(e)] != a[last_moved]) sum -= w[e];
    83         if (a[g.source(e)] == a[last_moved]) sum += w[e];
    84       }
    85       bool b = a[last_moved];
    86       a[last_moved] = !b;
    87     }
    88     Entity* clone() { return new Entity(*this); }
    89     void randomize() {
    90       for (NodeIt n(g); n != INVALID; ++n)
    91         a[n] = false;
    92       for (NodeIt n(g); n != INVALID; ++n)
    93         if (rand() < 0.5) a[n] = true;
    94       sum = 0;
    95       for (EdgeIt e(g); e != INVALID; ++e)
    96         if (a[g.source(e)] != a[g.target(e)])
    97           sum += w[e];
    98     }
    99 };
   100 
   101 int main()
   102 {
   103   Graph g;
   104   Graph::EdgeMap<int> w(g);
   105 
   106   GraphReader<Graph> reader("simann_maxcut_demo.lgf", g);
   107   reader.readEdgeMap("weight", w);
   108   reader.run();
   109 
   110   Entity e(g, w);
   111 
   112   SimAnn simann;
   113   SimpleController ctrl;
   114   simann.setController(ctrl);
   115   simann.setEntity(e);
   116   simann.run();
   117   
   118   Entity* be = (Entity *) simann.getBestEntity();
   119   std::cout << be->sum << std::endl;
   120   for (NodeIt n(g); n != INVALID; ++n)
   121     if (be->a[n]) std::cout << g.id(n) << ": 1" << std::endl;
   122     else std::cout << g.id(n) << ": 0" << std::endl;
   123 }