2 * demo/simann_maxcut_demo.cc - Part of LEMON, a generic C++ optimization
5 * Copyright (C) 2006 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
20 /// \brief A program demonstrating the simulated annealing algorithm class.
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.
26 /// \include simann_maxcut_demo.cc
31 #include <lemon/simann.h>
32 #include <lemon/list_graph.h>
33 #include <lemon/graph_reader.h>
35 using namespace lemon;
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;
45 class Entity : public EntityBase
49 Graph::EdgeMap<int>& w;
50 Graph::NodeMap<bool> a;
53 Entity(Graph& _g, Graph::EdgeMap<int>& _w) : g(_g), w(_w), a(_g) {}
55 static const int node_num = countNodes(g);
56 int i = 1 + (int) (node_num * (rand() / (RAND_MAX + 1.0)));
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];
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];
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];
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];
85 bool b = a[last_moved];
88 Entity* clone() { return new Entity(*this); }
90 for (NodeIt n(g); n != INVALID; ++n)
92 for (NodeIt n(g); n != INVALID; ++n)
93 if (rand() < 0.5) a[n] = true;
95 for (EdgeIt e(g); e != INVALID; ++e)
96 if (a[g.source(e)] != a[g.target(e)])
104 Graph::EdgeMap<int> w(g);
106 GraphReader<Graph> reader("simann_maxcut_demo.lgf", g);
107 reader.readEdgeMap("weight", w);
113 SimpleController ctrl;
114 simann.setController(ctrl);
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;