Added SimplePath::front().
3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
21 /// \brief A program demonstrating the simulated annealing algorithm class.
23 /// This program tries to find a maximal cut in a graph using simulated
24 /// annealing. It starts from a random solution and then in each step it
25 /// chooses a node and moves it to the other side of the cut.
27 /// \include simann_maxcut_demo.cc
32 #include <lemon/simann.h>
33 #include <lemon/list_graph.h>
34 #include <lemon/graph_reader.h>
36 using namespace lemon;
38 typedef ListGraph Graph;
39 typedef Graph::Node Node;
40 typedef Graph::Edge Edge;
41 typedef Graph::NodeIt NodeIt;
42 typedef Graph::EdgeIt EdgeIt;
43 typedef Graph::OutEdgeIt OutEdgeIt;
44 typedef Graph::InEdgeIt InEdgeIt;
46 class Entity : public EntityBase
50 Graph::EdgeMap<int>& w;
51 Graph::NodeMap<bool> a;
54 Entity(Graph& _g, Graph::EdgeMap<int>& _w) : g(_g), w(_w), a(_g) {}
56 static const int node_num = countNodes(g);
57 int i = 1 + rnd[node_num];
64 for (OutEdgeIt e(g, n); e != INVALID; ++e) {
65 if (a[n] != a[g.target(e)]) sum -= w[e];
66 if (a[n] == a[g.target(e)]) sum += w[e];
68 for (InEdgeIt e(g, n); e != INVALID; ++e) {
69 if (a[g.source(e)] != a[n]) sum -= w[e];
70 if (a[g.source(e)] == a[n]) sum += w[e];
78 for (OutEdgeIt e(g, last_moved); e != INVALID; ++e) {
79 if (a[last_moved] != a[g.target(e)]) sum -= w[e];
80 if (a[last_moved] == a[g.target(e)]) sum += w[e];
82 for (InEdgeIt e(g, last_moved); e != INVALID; ++e) {
83 if (a[g.source(e)] != a[last_moved]) sum -= w[e];
84 if (a[g.source(e)] == a[last_moved]) sum += w[e];
86 bool b = a[last_moved];
89 Entity* clone() { return new Entity(*this); }
91 for (NodeIt n(g); n != INVALID; ++n)
93 for (NodeIt n(g); n != INVALID; ++n)
94 if (rnd.boolean(0.5)) a[n] = true;
96 for (EdgeIt e(g); e != INVALID; ++e)
97 if (a[g.source(e)] != a[g.target(e)])
105 Graph::EdgeMap<int> w(g);
107 GraphReader<Graph> reader("simann_maxcut_demo.lgf", g);
108 reader.readEdgeMap("weight", w);
114 SimpleController ctrl;
115 simann.setController(ctrl);
119 Entity* be = static_cast<Entity*>(simann.getBestEntity());
120 std::cout << be->sum << std::endl;
121 for (NodeIt n(g); n != INVALID; ++n)
122 if (be->a[n]) std::cout << g.id(n) << ": 1" << std::endl;
123 else std::cout << g.id(n) << ": 0" << std::endl;