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