# HG changeset patch
# User deba
# Date 1146149603 0
# Node ID cd414bfbe38b4ab6c8183f531a25e7e76bde7653
# Parent  b72fe5e2631a54302736c4b37a70ad87b0f61788
Tabu Search by Szabadkai Mark

diff -r b72fe5e2631a -r cd414bfbe38b lemon/Makefile.am
--- a/lemon/Makefile.am	Thu Apr 27 13:10:23 2006 +0000
+++ b/lemon/Makefile.am	Thu Apr 27 14:53:23 2006 +0000
@@ -78,6 +78,7 @@
 	simann.h \
 	smart_graph.h \
 	sub_graph.h \
+	tabu_search.h \
 	time_measure.h \
 	topology.h \
 	ugraph_adaptor.h \
diff -r b72fe5e2631a -r cd414bfbe38b lemon/tabu_search.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/lemon/tabu_search.h	Thu Apr 27 14:53:23 2006 +0000
@@ -0,0 +1,530 @@
+/* -*- C++ -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2003-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.
+ *
+ */
+
+
+#ifndef LEMON_TABU_SEARCH_H
+#define LEMON_TABU_SEARCH_H
+
+/// \ingroup experimental
+/// \file
+/// \brief TabuSearch algorithm.
+///
+/// \author Szabadkai Mark
+
+#include <lemon/bits/utility.h>
+#include <lemon/error.h>
+#include <lemon/time_measure.h>
+#include <functional>
+#include <deque>
+
+
+namespace lemon {
+
+  /// \brief Default Traits for TabuSearch class.
+  /// 
+  /// This template defines the needed types for the \ref TabuSearch class.
+  /// Is main purpos is to simplify the main class's template interface,
+  /// but it provides the EdgeIt type, passing to the concrete graph wheter
+  /// it is directed or undirected.
+#ifdef DOXYGEN
+  template< typename GRAPH, typename VALUE, 
+            typename HEIGHTMAP, typename BETTER, bool UNDIR >
+#else
+  template< typename GRAPH, typename VALUE,
+            typename HEIGHTMAP = typename GRAPH::template NodeMap<VALUE>,
+            typename BETTER = std::less<VALUE>,
+            bool UNDIR = UndirectedTagIndicator<GRAPH>::value >
+#endif
+  struct TabuSearchDefaultTraits {
+    typedef  VALUE  Value; 
+    typedef  BETTER  Better;
+
+    typedef  GRAPH  Graph;
+    typedef  typename GRAPH::Node  Node;
+    typedef  HEIGHTMAP  HeightMap;
+
+    typedef  typename GRAPH::IncEdgeIt  EdgeIt;
+  };
+
+  template< typename GRAPH, typename VALUE, 
+            typename HEIGHTMAP, typename BETTER >
+  struct TabuSearchDefaultTraits< GRAPH, VALUE, HEIGHTMAP, BETTER, false > {
+    typedef  VALUE  Value;
+    typedef  BETTER  Better;
+
+    typedef  GRAPH  Graph;
+    typedef  typename GRAPH::Node  Node;
+    typedef  HEIGHTMAP  HeightMap;
+
+    typedef  typename GRAPH::OutEdgeIt  EdgeIt;
+  };
+
+
+
+  /// \brief Policy hierarchy to controll the search algorithm.
+  ///
+  /// The fallowing template hierarchy offers a clean interface to define own
+  /// policies, and combine existing ones.
+  template< typename TS >
+  struct TabuSearchPolicyConcept {
+    void  target( TS *ts ) {}
+
+    void  reset()  {}
+    bool  onStep() { return false; }
+    bool  onStick() { return false; }
+    bool  onImprove( const typename TS::Value &best ) { return false; }
+  };
+
+  template< typename TS >
+  struct YesPolicy {
+    void  target( TS *ts ) {}
+
+    void  reset()  {}
+    bool  onStep() { return true; }
+    bool  onStick() { return true; }
+    bool  onImprove( const typename TS::Value &best ) { return true; }
+  };
+
+  template< typename TS >
+  struct NoPolicy : public TabuSearchPolicyConcept<TS> {};
+
+  /// \brief Some basic methode, how tow Policies can be combined
+  struct PolicyAndCombination {
+    static bool  evaluate( const bool r1, const bool r2 ) {
+      return r1 && r2;
+    }
+  };
+
+  struct PolicyOrCombination {
+    static bool  evaluate( const bool r1, const bool r2 ) {
+      return r1 || r2;
+    }
+  };
+
+  /// \brief CombinePolicies
+  ///
+  /// It combines tow policies using the given combination methode (mainly
+  /// some of the basic logical methodes) to create a new one.
+#ifdef DOXYGEN
+  template< template<typename> class CP1, template<typename> class CP2, 
+            typename COMBINATION >
+#else
+  template< template<typename> class CP1, template<typename> class CP2,
+            typename COMBINATION = PolicyAndCombination >
+#endif
+  struct CombinePolicies {
+    template< typename TS >
+    struct Policy {
+      typedef CP1<TS>  Policy1;
+      typedef CP2<TS>  Policy2;
+      
+      Policy1  policy1;
+      Policy2  policy2;
+
+      inline Policy() : policy1(), policy2() {}
+      inline Policy( const Policy1 &cp1, const Policy2 &cp2 ) 
+        : policy1(cp1), policy2(cp2) {}
+
+      void  target( TS *ts ) {
+        policy1.target(ts), policy2.target(ts);
+      };
+
+      void  reset() {
+        policy1.reset(), policy2.reset();
+      }
+
+      bool  onStep() {
+        return cmb.evaluate( policy1.onStep(), policy2.onStep() );
+      }
+
+      bool  onStick() {
+        return cmb.evaluate( policy1.onStick(), policy2.onStick() );
+      }
+
+      bool  onImprove( const typename TS::Value &best ) {
+        return cmb.evaluate( policy1.onImprove(best), 
+                             policy2.onImprove(best) );
+      }
+
+    private:
+      COMBINATION cmb;
+    };
+  };
+
+
+  /// \brief IterationPolicy limits the number of iterations and the
+  /// number of iterations without improvement
+  template< typename TS >
+  struct IterationPolicy {
+    IterationPolicy() : _it_lim(100000), _noimpr_it_lim(5000) {}
+    IterationPolicy( const long int itl, const long int noimpritl )
+      : _it_lim(itl), _noimpr_it_lim(noimpritl)
+    {}
+
+    void  target( TS *ts ) {}
+
+    void  reset() {
+      _it = _noimpr_it = 0;
+    }
+
+    bool  onStep() {
+      ++_it; ++_noimpr_it;
+      return (_it <= _it_lim) && (_noimpr_it <= _noimpr_it_lim);
+    }
+		
+    bool  onStick() {
+      return false;
+    }
+
+    bool  onImprove( const typename TS::Value &best ) {
+      _noimpr_it = 0;
+      return true;
+    }
+
+    long int  iterationLimit() const {
+      return _it_lim;
+    }
+
+    void  iterationLimit( const long int itl ) {
+      _it_lim = itl;
+    }
+
+    long int  noImprovementIterationLimit() const {
+      return _noimpr_it_lim;
+    }
+
+    void  noImprovementIterationLimit( const long int noimpritl ) {
+      _noimpr_it_lim = noimpritl;
+    }
+
+  private:
+    long int  _it_lim, _noimpr_it_lim;
+    long int  _it, _noimpr_it;
+  };
+
+  /// \brief HeightPolicy stops the search when a given height is reached or
+  /// exceeds
+  template< typename TS >
+  struct HeightPolicy {
+    typedef typename TS::Value  Value;
+
+    HeightPolicy() : _height_lim(), _found(false) {}
+    HeightPolicy( const Value &hl ) : _height_lim(hl), _found(false) {}
+
+    void  target( TS *ts ) {}
+
+    void  reset() {
+      _found = false;
+    }
+
+    bool  onStep() {
+      return !_found;
+    }
+
+    bool  onStick() {
+      return false;
+    }
+
+    bool  onImprove( const Value &best ) {
+      typename TS::Better  better;
+      _found = better(best, _height_lim) || (best == _height_lim);
+      return !_found;
+    }
+
+    Value  heightLimi() const {
+      return _height_lim;
+    }
+
+    void  heightLimi( const Value &hl ) {
+      _height_lim = hl;
+    }
+
+  private:
+    Value  _height_lim;
+    bool  _found;
+  };
+
+  /// \brief TimePolicy limits the time for searching.
+  template< typename TS >
+  struct TimePolicy {
+    TimePolicy() : _time_lim(60.0), _timeisup(false) {}
+    TimePolicy( const double tl ) : _time_lim(tl), _timeisup(false) {}
+
+    void  target( TS *ts ) {}
+
+    void  reset() {
+      _timeisup = false;
+      _t.reset();
+    }
+
+    bool  onStep() {
+      update();
+      return !_timeisup;
+    }
+
+    bool  onStick() {
+      return false;
+    }
+
+    bool  onImprove( const typename TS::Value &best ) {
+      update();
+      return !_timeisup;
+    }
+
+    double timeLimit() const {
+      return _time_lim;
+    }
+
+    void  setTimeLimit( const double tl ) {
+      _time_lim = tl;
+      update();
+    }
+
+  private:
+    lemon::Timer  _t;
+    double  _time_lim;
+    bool  _timeisup;
+
+    inline void  update() {
+      _timeisup = _t.realTime() > _time_lim;
+    }
+  };
+
+
+
+  /// \brief TabuSearch main class
+  ///
+  /// This class offers the implementation of tabu-search algorithm. The
+  /// tabu-serach is a local-search. It starts from a specified point of the
+  /// problem's graph representation, and in every step it goes to the localy
+  /// best next Node except those in tabu set. The maximum size of this tabu
+  /// set defines how many Node will be remembered. The best Node ever found
+  /// will also stored, so we wont lose it, even is the search continues.
+  /// The class can be used on any kind of Graph and with any kind of Value
+  /// with a total-settlement on it.
+  ///
+  /// \param _Graph The graph type the algorithm runs on.
+  /// \param _Value The values' type associated to the nodes.
+  /// \param _Policy Controlls the search. Determinates when to stop, or how
+  /// manage stuck search. Default value is \ref IterationPolicy .
+  /// \param _Traits Collection of needed types. Default value is
+  /// \ref TabuSearchDefaultTraits .
+  ///
+  /// \author Szabadkai Mark
+#ifdef DOXYGEN
+  template< typename GRAPH, typename VALUE, template<typename> class POLICY, typename TRAITS >
+#else
+  template< typename GRAPH, typename VALUE,
+            template<typename> class POLICY = IterationPolicy,
+            typename TRAITS = TabuSearchDefaultTraits<GRAPH, VALUE> >
+#endif
+  class TabuSearch
+  {
+  public:
+
+    /// \brief Thrown by setting the size of the tabu-set and the given size
+    /// is less than 2.
+    class BadParameterError : public lemon::LogicError {
+    public:
+      virtual const char* exceptionName() const {
+        return "lemon::TabuSearch::BadParameterError";
+      }
+    };
+
+    ///Public types
+    typedef  TabuSearch<GRAPH,VALUE,POLICY,TRAITS>  SelfType;
+
+    typedef  typename TRAITS::Graph  Graph;
+    typedef  typename TRAITS::Node  Node;
+    typedef  typename TRAITS::Value  Value;
+    typedef  typename TRAITS::HeightMap  HeightMap;
+    typedef  typename TRAITS::Better  Better;
+    typedef  typename std::deque< Node >::const_iterator  TabuIterator;
+
+    typedef  POLICY<SelfType>  Policy;
+
+  protected:
+    typedef  typename TRAITS::EdgeIt  EdgeIt;
+
+    const Graph  &gr;
+    const HeightMap  &height;
+    /// The tabu set. Teh current node is the first
+    std::deque< Node >  tabu;
+    /// Maximal tabu size
+    unsigned int  mts;
+    /// The best Node found
+    Node  b;
+
+    Better  better;
+    Policy  pol;
+
+  public:
+    /// \brief Constructor
+    ///
+    /// \param graph the graph the algorithm will run on.
+    /// \param hm the height map used by the algorithm.
+    /// \param tabusz the maximal size of the tabu set. Default value is 3
+    /// \param p the Policy controlling the search.
+    TabuSearch( const Graph &graph, const HeightMap &hm, 
+                const int tabusz = 3, Policy p = Policy() )
+      : gr(graph), height(hm), mts(tabusz), pol(p)
+    {
+      pol.target(this);
+    }
+
+    /// \brief Destructor
+    ~TabuSearch() {
+      pol.target(NULL);
+    }
+
+    /// Set/Get the size of the tabu set
+    void  tabuSize( const unsigned int size )
+    {
+      if( size < 2 )
+      throw BadParameterError( "Tabu size must be at least 2!" );
+      mts = size;
+      while( mts < tabu.size() )
+      tabu.pop_back();
+    }
+
+    unsigned int  tabuSize() const {
+      return mts;
+    }
+
+    /// Set/Get Policy
+    void  policy( Policy p ) {
+      pol.target(NULL);
+      pol = p;
+      pol.target(this);
+    }
+		
+    Policy& policy()  {
+      return pol;
+    }
+
+    /// \name Execution control
+    /// The simplest way to execute the algorithm is to use the member
+    /// functions called \c run( 'startnode' ).
+    ///@{
+
+    /// \brief Initializes the internal data.
+    ///
+    /// \param startn The start node where the search begins.
+    void  init( const Node startn ) {
+      tabu.clear();
+      tabu.push_front( startn );
+      b = startn;
+      pol.reset();
+    }
+
+    /// \brief Does one iteration
+    ///
+    /// If the Policy allows it searches for the best next node, then steps
+    /// onto it.
+    /// \return %False if one Policy condition wants to stop the search.
+    bool  step()
+    {
+      ///Request premmision from ControllPolicy
+      if( !pol.onStep() )
+      return false;
+	
+      ///Find the best next potential node
+      Node n; bool found = false;
+      for( EdgeIt e(gr,tabu[0]); e != INVALID; ++e )
+      {
+        Node m = (gr.source(e) == tabu[0]) ? gr.target(e) : gr.source(e);
+        bool wrong = false;
+        for( int i = 1; i != (signed int)tabu.size(); ++i )
+          if( m == tabu[i] ) {
+            wrong = true;
+            break;
+          }
+        if( wrong )
+          continue;
+
+        if( !found ) {
+          n = m;
+          found = true;
+        } else
+          if( better(height[m], height[n]) ) {
+            n = m;
+          }
+      }
+
+      ///Handle stuck search
+      if( !found ) {
+        return pol.onStick();
+      }
+
+      ///Move on...
+      tabu.push_front(n);
+      while( mts < tabu.size() ) {
+        tabu.pop_back();
+      }
+      if( better(height[n], height[b]) ) {
+        b = n;
+        if( !pol.onImprove(height[b]) )
+        return false;
+      }
+
+      return true;
+    }
+
+    /// \brief Runs a search while the Policy stops it.
+    ///
+    /// \param startn The start node where the search begins.
+    inline void  run( const Node startn ) {
+      std::cin.unsetf( std::ios_base::skipws );
+      char c;
+      init( startn );
+      while( step() )
+      std::cin >> c;
+      std::cin.setf( std::ios_base::skipws );
+    }
+
+    ///@}
+
+    /// \name Query Functions
+    /// The result of the TabuSearch algorithm can be obtained using these
+    /// functions.\n
+    ///@{
+
+    /// \brief The node, the search is standing on.
+    inline Node  current() const {
+      return tabu[0];
+    }
+
+    /// \brief The best node found until now.
+    inline Node  best() const {
+      return b;
+    }
+
+    /// \brief Beginning to iterate on the current tabu set.
+    inline TabuIterator  tabu_begin() const {
+      return tabu.begin();
+    }
+
+    /// \brief Ending to iterate on the current tabu set.
+    inline TabuIterator  tabu_end() const {
+      return tabu.end();
+    }
+
+    ///@}
+  };
+}
+#endif