ladanyi@1919: /* -*- C++ -*- ladanyi@1919: * alpar@1956: * This file is a part of LEMON, a generic C++ optimization library alpar@1956: * alpar@2553: * Copyright (C) 2003-2008 alpar@1956: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport ladanyi@1919: * (Egervary Research Group on Combinatorial Optimization, EGRES). ladanyi@1919: * ladanyi@1919: * Permission to use, modify and distribute this software is granted ladanyi@1919: * provided that this copyright notice appears in all copies. For ladanyi@1919: * precise terms see the accompanying LICENSE file. ladanyi@1919: * ladanyi@1919: * This software is provided "AS IS" with no warranty of any kind, ladanyi@1919: * express or implied, and with no claim as to its suitability for any ladanyi@1919: * purpose. ladanyi@1919: * ladanyi@1919: */ ladanyi@1919: ladanyi@1919: /// \ingroup demos ladanyi@1919: /// \file ladanyi@1919: /// \brief A program demonstrating the simulated annealing algorithm class. ladanyi@1919: /// ladanyi@1919: /// This program tries to find a maximal cut in a graph using simulated ladanyi@1919: /// annealing. It starts from a random solution and then in each step it ladanyi@1919: /// chooses a node and moves it to the other side of the cut. ladanyi@1919: /// ladanyi@1919: /// \include simann_maxcut_demo.cc ladanyi@1919: ladanyi@1919: #include ladanyi@1919: #include ladanyi@1919: ladanyi@1919: #include ladanyi@1919: #include ladanyi@1919: #include ladanyi@1919: ladanyi@1919: using namespace lemon; ladanyi@1919: ladanyi@1919: typedef ListGraph Graph; ladanyi@1919: typedef Graph::Node Node; ladanyi@1919: typedef Graph::Edge Edge; ladanyi@1919: typedef Graph::NodeIt NodeIt; ladanyi@1919: typedef Graph::EdgeIt EdgeIt; ladanyi@1919: typedef Graph::OutEdgeIt OutEdgeIt; ladanyi@1919: typedef Graph::InEdgeIt InEdgeIt; ladanyi@1919: ladanyi@1919: class Entity : public EntityBase ladanyi@1919: { ladanyi@1919: public: ladanyi@1919: Graph& g; ladanyi@1919: Graph::EdgeMap& w; ladanyi@1919: Graph::NodeMap a; ladanyi@1919: int sum; ladanyi@1919: Node last_moved; ladanyi@1919: Entity(Graph& _g, Graph::EdgeMap& _w) : g(_g), w(_w), a(_g) {} ladanyi@1919: double mutate() { ladanyi@1919: static const int node_num = countNodes(g); deba@2242: int i = 1 + rnd[node_num]; ladanyi@1919: NodeIt n(g); ladanyi@1919: int j = 1; ladanyi@1919: while (j < i) { ladanyi@1919: ++n; ladanyi@1919: ++j; ladanyi@1919: } ladanyi@1919: for (OutEdgeIt e(g, n); e != INVALID; ++e) { ladanyi@1919: if (a[n] != a[g.target(e)]) sum -= w[e]; ladanyi@1919: if (a[n] == a[g.target(e)]) sum += w[e]; ladanyi@1919: } ladanyi@1919: for (InEdgeIt e(g, n); e != INVALID; ++e) { ladanyi@1919: if (a[g.source(e)] != a[n]) sum -= w[e]; ladanyi@1919: if (a[g.source(e)] == a[n]) sum += w[e]; ladanyi@1919: } ladanyi@1919: bool b = a[n]; ladanyi@1919: a[n] = !b; ladanyi@1919: last_moved = n; ladanyi@1919: return -sum; ladanyi@1919: } ladanyi@1919: void revert() { ladanyi@1919: for (OutEdgeIt e(g, last_moved); e != INVALID; ++e) { ladanyi@1919: if (a[last_moved] != a[g.target(e)]) sum -= w[e]; ladanyi@1919: if (a[last_moved] == a[g.target(e)]) sum += w[e]; ladanyi@1919: } ladanyi@1919: for (InEdgeIt e(g, last_moved); e != INVALID; ++e) { ladanyi@1919: if (a[g.source(e)] != a[last_moved]) sum -= w[e]; ladanyi@1919: if (a[g.source(e)] == a[last_moved]) sum += w[e]; ladanyi@1919: } ladanyi@1919: bool b = a[last_moved]; ladanyi@1919: a[last_moved] = !b; ladanyi@1919: } ladanyi@1919: Entity* clone() { return new Entity(*this); } ladanyi@1919: void randomize() { ladanyi@1919: for (NodeIt n(g); n != INVALID; ++n) ladanyi@1919: a[n] = false; ladanyi@1919: for (NodeIt n(g); n != INVALID; ++n) deba@2242: if (rnd.boolean(0.5)) a[n] = true; ladanyi@1919: sum = 0; ladanyi@1919: for (EdgeIt e(g); e != INVALID; ++e) ladanyi@1919: if (a[g.source(e)] != a[g.target(e)]) ladanyi@1919: sum += w[e]; ladanyi@1919: } ladanyi@1919: }; ladanyi@1919: ladanyi@1919: int main() ladanyi@1919: { ladanyi@1919: Graph g; ladanyi@1919: Graph::EdgeMap w(g); ladanyi@1919: ladanyi@1919: GraphReader reader("simann_maxcut_demo.lgf", g); ladanyi@1919: reader.readEdgeMap("weight", w); ladanyi@1919: reader.run(); ladanyi@1919: ladanyi@1919: Entity e(g, w); ladanyi@1919: ladanyi@1919: SimAnn simann; ladanyi@1919: SimpleController ctrl; ladanyi@1919: simann.setController(ctrl); ladanyi@1919: simann.setEntity(e); ladanyi@1919: simann.run(); ladanyi@1919: deba@2386: Entity* be = static_cast(simann.getBestEntity()); ladanyi@1919: std::cout << be->sum << std::endl; ladanyi@1919: for (NodeIt n(g); n != INVALID; ++n) ladanyi@1919: if (be->a[n]) std::cout << g.id(n) << ": 1" << std::endl; ladanyi@1919: else std::cout << g.id(n) << ": 0" << std::endl; ladanyi@1919: }