demo/simann_maxcut_demo.cc
author deba
Wed, 01 Mar 2006 10:25:30 +0000
changeset 1991 d7442141d9ef
parent 1919 9704601de87f
child 2242 16523135943d
permissions -rw-r--r--
The graph adadptors can be alteration observed.
In most cases it uses the adapted graph alteration notifiers.
Only special case is now the UndirGraphAdaptor, where
we have to proxy the signals from the graph.

The SubBidirGraphAdaptor is removed, because it doest not
gives more feature than the EdgeSubGraphAdaptor<UndirGraphAdaptor<Graph>>.

The ResGraphAdaptor is based on this composition.
     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 
    36 using namespace lemon;
    37 
    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;
    45 
    46 class 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 
   102 int 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 }