COIN-OR::LEMON - Graph Library

source: lemon-0.x/demo/simann_maxcut_demo.cc @ 1975:64db671eda28

Last change on this file since 1975:64db671eda28 was 1956:a055123339d5, checked in by Alpar Juttner, 18 years ago

Unified copyright notices

File size: 3.4 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19/// \ingroup demos
20/// \file
21/// \brief A program demonstrating the simulated annealing algorithm class.
22///
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.
26///
27/// \include simann_maxcut_demo.cc
28
29#include <iostream>
30#include <cstdlib>
31
32#include <lemon/simann.h>
33#include <lemon/list_graph.h>
34#include <lemon/graph_reader.h>
35
36using namespace lemon;
37
38typedef ListGraph Graph;
39typedef Graph::Node Node;
40typedef Graph::Edge Edge;
41typedef Graph::NodeIt NodeIt;
42typedef Graph::EdgeIt EdgeIt;
43typedef Graph::OutEdgeIt OutEdgeIt;
44typedef Graph::InEdgeIt InEdgeIt;
45
46class Entity : public EntityBase
47{
48  public:
49    Graph& g;
50    Graph::EdgeMap<int>& w;
51    Graph::NodeMap<bool> a;
52    int sum;
53    Node last_moved;
54    Entity(Graph& _g, Graph::EdgeMap<int>& _w) : g(_g), w(_w), a(_g) {}
55    double mutate() {
56      static const int node_num = countNodes(g);
57      int i = 1 + (int) (node_num * (rand() / (RAND_MAX + 1.0)));
58      NodeIt n(g);
59      int j = 1;
60      while (j < i) {
61        ++n;
62        ++j;
63      }
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];
67      }
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];
71      }
72      bool b = a[n];
73      a[n] = !b;
74      last_moved = n;
75      return -sum;
76    }
77    void revert() {
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];
81      }
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];
85      }
86      bool b = a[last_moved];
87      a[last_moved] = !b;
88    }
89    Entity* clone() { return new Entity(*this); }
90    void randomize() {
91      for (NodeIt n(g); n != INVALID; ++n)
92        a[n] = false;
93      for (NodeIt n(g); n != INVALID; ++n)
94        if (rand() < 0.5) a[n] = true;
95      sum = 0;
96      for (EdgeIt e(g); e != INVALID; ++e)
97        if (a[g.source(e)] != a[g.target(e)])
98          sum += w[e];
99    }
100};
101
102int main()
103{
104  Graph g;
105  Graph::EdgeMap<int> w(g);
106
107  GraphReader<Graph> reader("simann_maxcut_demo.lgf", g);
108  reader.readEdgeMap("weight", w);
109  reader.run();
110
111  Entity e(g, w);
112
113  SimAnn simann;
114  SimpleController ctrl;
115  simann.setController(ctrl);
116  simann.setEntity(e);
117  simann.run();
118 
119  Entity* be = (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;
124}
Note: See TracBrowser for help on using the repository browser.