|
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 } |