COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/simann_maxcut_demo.cc @ 1919:9704601de87f

Last change on this file since 1919:9704601de87f was 1919:9704601de87f, checked in by Akos Ladanyi, 14 years ago

demo for simann

File size: 3.4 KB
Line 
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
35using namespace lemon;
36
37typedef ListGraph Graph;
38typedef Graph::Node Node;
39typedef Graph::Edge Edge;
40typedef Graph::NodeIt NodeIt;
41typedef Graph::EdgeIt EdgeIt;
42typedef Graph::OutEdgeIt OutEdgeIt;
43typedef Graph::InEdgeIt InEdgeIt;
44
45class 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
101int 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}
Note: See TracBrowser for help on using the repository browser.