1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/demo/simann_maxcut_demo.cc	Sun Jan 29 22:06:45 2006 +0000
     1.3 @@ -0,0 +1,123 @@
     1.4 +/* -*- C++ -*-
     1.5 + * demo/simann_maxcut_demo.cc - Part of LEMON, a generic C++ optimization
     1.6 + * library
     1.7 + *
     1.8 + * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     1.9 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
    1.10 + *
    1.11 + * Permission to use, modify and distribute this software is granted
    1.12 + * provided that this copyright notice appears in all copies. For
    1.13 + * precise terms see the accompanying LICENSE file.
    1.14 + *
    1.15 + * This software is provided "AS IS" with no warranty of any kind,
    1.16 + * express or implied, and with no claim as to its suitability for any
    1.17 + * purpose.
    1.18 + *
    1.19 + */
    1.20 +
    1.21 +/// \ingroup demos
    1.22 +/// \file
    1.23 +/// \brief A program demonstrating the simulated annealing algorithm class.
    1.24 +///
    1.25 +/// This program tries to find a maximal cut in a graph using simulated
    1.26 +/// annealing. It starts from a random solution and then in each step it
    1.27 +/// chooses a node and moves it to the other side of the cut.
    1.28 +///
    1.29 +/// \include simann_maxcut_demo.cc
    1.30 +
    1.31 +#include <iostream>
    1.32 +#include <cstdlib>
    1.33 +
    1.34 +#include <lemon/simann.h>
    1.35 +#include <lemon/list_graph.h>
    1.36 +#include <lemon/graph_reader.h>
    1.37 +
    1.38 +using namespace lemon;
    1.39 +
    1.40 +typedef ListGraph Graph;
    1.41 +typedef Graph::Node Node;
    1.42 +typedef Graph::Edge Edge;
    1.43 +typedef Graph::NodeIt NodeIt;
    1.44 +typedef Graph::EdgeIt EdgeIt;
    1.45 +typedef Graph::OutEdgeIt OutEdgeIt;
    1.46 +typedef Graph::InEdgeIt InEdgeIt;
    1.47 +
    1.48 +class Entity : public EntityBase
    1.49 +{
    1.50 +  public:
    1.51 +    Graph& g;
    1.52 +    Graph::EdgeMap<int>& w;
    1.53 +    Graph::NodeMap<bool> a;
    1.54 +    int sum;
    1.55 +    Node last_moved;
    1.56 +    Entity(Graph& _g, Graph::EdgeMap<int>& _w) : g(_g), w(_w), a(_g) {}
    1.57 +    double mutate() {
    1.58 +      static const int node_num = countNodes(g);
    1.59 +      int i = 1 + (int) (node_num * (rand() / (RAND_MAX + 1.0)));
    1.60 +      NodeIt n(g);
    1.61 +      int j = 1;
    1.62 +      while (j < i) {
    1.63 +        ++n;
    1.64 +        ++j;
    1.65 +      }
    1.66 +      for (OutEdgeIt e(g, n); e != INVALID; ++e) {
    1.67 +        if (a[n] != a[g.target(e)]) sum -= w[e];
    1.68 +        if (a[n] == a[g.target(e)]) sum += w[e];
    1.69 +      }
    1.70 +      for (InEdgeIt e(g, n); e != INVALID; ++e) {
    1.71 +        if (a[g.source(e)] != a[n]) sum -= w[e];
    1.72 +        if (a[g.source(e)] == a[n]) sum += w[e];
    1.73 +      }
    1.74 +      bool b = a[n];
    1.75 +      a[n] = !b;
    1.76 +      last_moved = n;
    1.77 +      return -sum;
    1.78 +    }
    1.79 +    void revert() {
    1.80 +      for (OutEdgeIt e(g, last_moved); e != INVALID; ++e) {
    1.81 +        if (a[last_moved] != a[g.target(e)]) sum -= w[e];
    1.82 +        if (a[last_moved] == a[g.target(e)]) sum += w[e];
    1.83 +      }
    1.84 +      for (InEdgeIt e(g, last_moved); e != INVALID; ++e) {
    1.85 +        if (a[g.source(e)] != a[last_moved]) sum -= w[e];
    1.86 +        if (a[g.source(e)] == a[last_moved]) sum += w[e];
    1.87 +      }
    1.88 +      bool b = a[last_moved];
    1.89 +      a[last_moved] = !b;
    1.90 +    }
    1.91 +    Entity* clone() { return new Entity(*this); }
    1.92 +    void randomize() {
    1.93 +      for (NodeIt n(g); n != INVALID; ++n)
    1.94 +        a[n] = false;
    1.95 +      for (NodeIt n(g); n != INVALID; ++n)
    1.96 +        if (rand() < 0.5) a[n] = true;
    1.97 +      sum = 0;
    1.98 +      for (EdgeIt e(g); e != INVALID; ++e)
    1.99 +        if (a[g.source(e)] != a[g.target(e)])
   1.100 +          sum += w[e];
   1.101 +    }
   1.102 +};
   1.103 +
   1.104 +int main()
   1.105 +{
   1.106 +  Graph g;
   1.107 +  Graph::EdgeMap<int> w(g);
   1.108 +
   1.109 +  GraphReader<Graph> reader("simann_maxcut_demo.lgf", g);
   1.110 +  reader.readEdgeMap("weight", w);
   1.111 +  reader.run();
   1.112 +
   1.113 +  Entity e(g, w);
   1.114 +
   1.115 +  SimAnn simann;
   1.116 +  SimpleController ctrl;
   1.117 +  simann.setController(ctrl);
   1.118 +  simann.setEntity(e);
   1.119 +  simann.run();
   1.120 +  
   1.121 +  Entity* be = (Entity *) simann.getBestEntity();
   1.122 +  std::cout << be->sum << std::endl;
   1.123 +  for (NodeIt n(g); n != INVALID; ++n)
   1.124 +    if (be->a[n]) std::cout << g.id(n) << ": 1" << std::endl;
   1.125 +    else std::cout << g.id(n) << ": 0" << std::endl;
   1.126 +}

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/demo/simann_maxcut_demo.lgf	Sun Jan 29 22:06:45 2006 +0000
     2.3 @@ -0,0 +1,22 @@
     2.4 +@nodeset
     2.5 +label
     2.6 +0
     2.7 +1
     2.8 +2
     2.9 +3
    2.10 +4
    2.11 +5
    2.12 +6
    2.13 +@edgeset
    2.14 +        weight
    2.15 +0   3   1
    2.16 +0   4   1
    2.17 +1   5   1
    2.18 +5   2   1
    2.19 +6   2   1
    2.20 +0   1   1
    2.21 +2   1   1
    2.22 +3   4   1
    2.23 +4   5   1
    2.24 +5   6   1
    2.25 +@end