lemon/grosso_locatelli_pullan_mc.h
changeset 918 8583fb74238c
parent 904 c279b19abc62
child 1053 1c978b5bcc65
     1.1 --- a/lemon/grosso_locatelli_pullan_mc.h	Tue Nov 16 07:46:01 2010 +0100
     1.2 +++ b/lemon/grosso_locatelli_pullan_mc.h	Sat Jan 08 15:52:07 2011 +0100
     1.3 @@ -46,8 +46,12 @@
     1.4    /// pair of nodes is connected.
     1.5    ///
     1.6    /// This class provides a simple but highly efficient and robust heuristic
     1.7 -  /// method that quickly finds a large clique, but not necessarily the
     1.8 +  /// method that quickly finds a quite large clique, but not necessarily the
     1.9    /// largest one.
    1.10 +  /// The algorithm performs a certain number of iterations to find several
    1.11 +  /// cliques and selects the largest one among them. Various limits can be
    1.12 +  /// specified to control the running time and the effectiveness of the
    1.13 +  /// search process.
    1.14    ///
    1.15    /// \tparam GR The undirected graph type the algorithm runs on.
    1.16    ///
    1.17 @@ -84,6 +88,22 @@
    1.18        PENALTY_BASED
    1.19      };
    1.20  
    1.21 +    /// \brief Constants for the causes of search termination.
    1.22 +    ///
    1.23 +    /// Enum type containing constants for the different causes of search
    1.24 +    /// termination. The \ref run() function returns one of these values.
    1.25 +    enum TerminationCause {
    1.26 +
    1.27 +      /// The iteration count limit is reached.
    1.28 +      ITERATION_LIMIT,
    1.29 +
    1.30 +      /// The step count limit is reached.
    1.31 +      STEP_LIMIT,
    1.32 +
    1.33 +      /// The clique size limit is reached.
    1.34 +      SIZE_LIMIT
    1.35 +    };
    1.36 +
    1.37    private:
    1.38  
    1.39      TEMPLATE_GRAPH_TYPEDEFS(GR);
    1.40 @@ -93,12 +113,22 @@
    1.41      typedef std::vector<BoolVector> BoolMatrix;
    1.42      // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    1.43  
    1.44 +    // The underlying graph
    1.45      const GR &_graph;
    1.46      IntNodeMap _id;
    1.47  
    1.48      // Internal matrix representation of the graph
    1.49      BoolMatrix _gr;
    1.50      int _n;
    1.51 +    
    1.52 +    // Search options
    1.53 +    bool _delta_based_restart;
    1.54 +    int _restart_delta_limit;
    1.55 + 
    1.56 +    // Search limits
    1.57 +    int _iteration_limit;
    1.58 +    int _step_limit;
    1.59 +    int _size_limit;
    1.60  
    1.61      // The current clique
    1.62      BoolVector _clique;
    1.63 @@ -380,7 +410,9 @@
    1.64      /// \param graph The undirected graph the algorithm runs on.
    1.65      GrossoLocatelliPullanMc(const GR& graph) :
    1.66        _graph(graph), _id(_graph), _rnd(rnd)
    1.67 -    {}
    1.68 +    {
    1.69 +      initOptions();
    1.70 +    }
    1.71  
    1.72      /// \brief Constructor with random seed.
    1.73      ///
    1.74 @@ -391,7 +423,9 @@
    1.75      /// that is used during the algorithm.
    1.76      GrossoLocatelliPullanMc(const GR& graph, int seed) :
    1.77        _graph(graph), _id(_graph), _rnd(seed)
    1.78 -    {}
    1.79 +    {
    1.80 +      initOptions();
    1.81 +    }
    1.82  
    1.83      /// \brief Constructor with random number generator.
    1.84      ///
    1.85 @@ -402,43 +436,155 @@
    1.86      /// algorithm.
    1.87      GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
    1.88        _graph(graph), _id(_graph), _rnd(random)
    1.89 -    {}
    1.90 +    {
    1.91 +      initOptions();
    1.92 +    }
    1.93  
    1.94      /// \name Execution Control
    1.95 +    /// The \ref run() function can be used to execute the algorithm.\n
    1.96 +    /// The functions \ref iterationLimit(int), \ref stepLimit(int), and 
    1.97 +    /// \ref sizeLimit(int) can be used to specify various limits for the
    1.98 +    /// search process.
    1.99 +    
   1.100      /// @{
   1.101 +    
   1.102 +    /// \brief Sets the maximum number of iterations.
   1.103 +    ///
   1.104 +    /// This function sets the maximum number of iterations.
   1.105 +    /// Each iteration of the algorithm finds a maximal clique (but not
   1.106 +    /// necessarily the largest one) by performing several search steps
   1.107 +    /// (node selections).
   1.108 +    ///
   1.109 +    /// This limit controls the running time and the success of the
   1.110 +    /// algorithm. For larger values, the algorithm runs slower, but it more
   1.111 +    /// likely finds larger cliques. For smaller values, the algorithm is
   1.112 +    /// faster but probably gives worse results.
   1.113 +    /// 
   1.114 +    /// The default value is \c 1000.
   1.115 +    /// \c -1 means that number of iterations is not limited.
   1.116 +    ///
   1.117 +    /// \warning You should specify a reasonable limit for the number of
   1.118 +    /// iterations and/or the number of search steps.
   1.119 +    ///
   1.120 +    /// \return <tt>(*this)</tt>
   1.121 +    ///
   1.122 +    /// \sa stepLimit(int)
   1.123 +    /// \sa sizeLimit(int)
   1.124 +    GrossoLocatelliPullanMc& iterationLimit(int limit) {
   1.125 +      _iteration_limit = limit;
   1.126 +      return *this;
   1.127 +    }
   1.128 +    
   1.129 +    /// \brief Sets the maximum number of search steps.
   1.130 +    ///
   1.131 +    /// This function sets the maximum number of elementary search steps.
   1.132 +    /// Each iteration of the algorithm finds a maximal clique (but not
   1.133 +    /// necessarily the largest one) by performing several search steps
   1.134 +    /// (node selections).
   1.135 +    ///
   1.136 +    /// This limit controls the running time and the success of the
   1.137 +    /// algorithm. For larger values, the algorithm runs slower, but it more
   1.138 +    /// likely finds larger cliques. For smaller values, the algorithm is
   1.139 +    /// faster but probably gives worse results.
   1.140 +    /// 
   1.141 +    /// The default value is \c -1, which means that number of steps
   1.142 +    /// is not limited explicitly. However, the number of iterations is
   1.143 +    /// limited and each iteration performs a finite number of search steps.
   1.144 +    ///
   1.145 +    /// \warning You should specify a reasonable limit for the number of
   1.146 +    /// iterations and/or the number of search steps.
   1.147 +    ///
   1.148 +    /// \return <tt>(*this)</tt>
   1.149 +    ///
   1.150 +    /// \sa iterationLimit(int)
   1.151 +    /// \sa sizeLimit(int)
   1.152 +    GrossoLocatelliPullanMc& stepLimit(int limit) {
   1.153 +      _step_limit = limit;
   1.154 +      return *this;
   1.155 +    }
   1.156 +    
   1.157 +    /// \brief Sets the desired clique size.
   1.158 +    ///
   1.159 +    /// This function sets the desired clique size that serves as a search
   1.160 +    /// limit. If a clique of this size (or a larger one) is found, then the
   1.161 +    /// algorithm terminates.
   1.162 +    /// 
   1.163 +    /// This function is especially useful if you know an exact upper bound
   1.164 +    /// for the size of the cliques in the graph or if any clique above 
   1.165 +    /// a certain size limit is sufficient for your application.
   1.166 +    /// 
   1.167 +    /// The default value is \c -1, which means that the size limit is set to
   1.168 +    /// the number of nodes in the graph.
   1.169 +    ///
   1.170 +    /// \return <tt>(*this)</tt>
   1.171 +    ///
   1.172 +    /// \sa iterationLimit(int)
   1.173 +    /// \sa stepLimit(int)
   1.174 +    GrossoLocatelliPullanMc& sizeLimit(int limit) {
   1.175 +      _size_limit = limit;
   1.176 +      return *this;
   1.177 +    }
   1.178 +    
   1.179 +    /// \brief The maximum number of iterations.
   1.180 +    ///
   1.181 +    /// This function gives back the maximum number of iterations.
   1.182 +    /// \c -1 means that no limit is specified.
   1.183 +    ///
   1.184 +    /// \sa iterationLimit(int)
   1.185 +    int iterationLimit() const {
   1.186 +      return _iteration_limit;
   1.187 +    }
   1.188 +    
   1.189 +    /// \brief The maximum number of search steps.
   1.190 +    ///
   1.191 +    /// This function gives back the maximum number of search steps.
   1.192 +    /// \c -1 means that no limit is specified.
   1.193 +    ///
   1.194 +    /// \sa stepLimit(int)
   1.195 +    int stepLimit() const {
   1.196 +      return _step_limit;
   1.197 +    }
   1.198 +    
   1.199 +    /// \brief The desired clique size.
   1.200 +    ///
   1.201 +    /// This function gives back the desired clique size that serves as a
   1.202 +    /// search limit. \c -1 means that this limit is set to the number of
   1.203 +    /// nodes in the graph.
   1.204 +    ///
   1.205 +    /// \sa sizeLimit(int)
   1.206 +    int sizeLimit() const {
   1.207 +      return _size_limit;
   1.208 +    }
   1.209  
   1.210      /// \brief Runs the algorithm.
   1.211      ///
   1.212 -    /// This function runs the algorithm.
   1.213 +    /// This function runs the algorithm. If one of the specified limits
   1.214 +    /// is reached, the search process terminates.
   1.215      ///
   1.216 -    /// \param step_num The maximum number of node selections (steps)
   1.217 -    /// during the search process.
   1.218 -    /// This parameter controls the running time and the success of the
   1.219 -    /// algorithm. For larger values, the algorithm runs slower but it more
   1.220 -    /// likely finds larger cliques. For smaller values, the algorithm is
   1.221 -    /// faster but probably gives worse results.
   1.222      /// \param rule The node selection rule. For more information, see
   1.223      /// \ref SelectionRule.
   1.224      ///
   1.225 -    /// \return The size of the found clique.
   1.226 -    int run(int step_num = 100000,
   1.227 -            SelectionRule rule = PENALTY_BASED)
   1.228 +    /// \return The termination cause of the search. For more information,
   1.229 +    /// see \ref TerminationCause.
   1.230 +    TerminationCause run(SelectionRule rule = PENALTY_BASED)
   1.231      {
   1.232        init();
   1.233        switch (rule) {
   1.234          case RANDOM:
   1.235 -          return start<RandomSelectionRule>(step_num);
   1.236 +          return start<RandomSelectionRule>();
   1.237          case DEGREE_BASED:
   1.238 -          return start<DegreeBasedSelectionRule>(step_num);
   1.239 -        case PENALTY_BASED:
   1.240 -          return start<PenaltyBasedSelectionRule>(step_num);
   1.241 +          return start<DegreeBasedSelectionRule>();
   1.242 +        default:
   1.243 +          return start<PenaltyBasedSelectionRule>();
   1.244        }
   1.245 -      return 0; // avoid warning
   1.246      }
   1.247  
   1.248      /// @}
   1.249  
   1.250      /// \name Query Functions
   1.251 +    /// The results of the algorithm can be obtained using these functions.\n
   1.252 +    /// The run() function must be called before using them. 
   1.253 +
   1.254      /// @{
   1.255  
   1.256      /// \brief The size of the found clique
   1.257 @@ -530,6 +676,18 @@
   1.258      /// @}
   1.259  
   1.260    private:
   1.261 +  
   1.262 +    // Initialize search options and limits
   1.263 +    void initOptions() {
   1.264 +      // Search options
   1.265 +      _delta_based_restart = true;
   1.266 +      _restart_delta_limit = 4;
   1.267 +     
   1.268 +      // Search limits
   1.269 +      _iteration_limit = 1000;
   1.270 +      _step_limit = -1;             // this is disabled by default
   1.271 +      _size_limit = -1;             // this is disabled by default
   1.272 +    }
   1.273  
   1.274      // Adds a node to the current clique
   1.275      void addCliqueNode(int u) {
   1.276 @@ -586,30 +744,32 @@
   1.277  
   1.278      // Executes the algorithm
   1.279      template <typename SelectionRuleImpl>
   1.280 -    int start(int max_select) {
   1.281 -      // Options for the restart rule
   1.282 -      const bool delta_based_restart = true;
   1.283 -      const int restart_delta_limit = 4;
   1.284 -
   1.285 -      if (_n == 0) return 0;
   1.286 +    TerminationCause start() {
   1.287 +      if (_n == 0) return SIZE_LIMIT;
   1.288        if (_n == 1) {
   1.289          _best_clique[0] = true;
   1.290          _best_size = 1;
   1.291 -        return _best_size;
   1.292 +        return SIZE_LIMIT;
   1.293        }
   1.294  
   1.295 -      // Iterated local search
   1.296 +      // Iterated local search algorithm
   1.297 +      const int max_size = _size_limit >= 0 ? _size_limit : _n;
   1.298 +      const int max_restart = _iteration_limit >= 0 ?
   1.299 +        _iteration_limit : std::numeric_limits<int>::max();
   1.300 +      const int max_select = _step_limit >= 0 ?
   1.301 +        _step_limit : std::numeric_limits<int>::max();
   1.302 +
   1.303        SelectionRuleImpl sel_method(*this);
   1.304 -      int select = 0;
   1.305 +      int select = 0, restart = 0;
   1.306        IntVector restart_nodes;
   1.307 -
   1.308 -      while (select < max_select) {
   1.309 +      while (select < max_select && restart < max_restart) {
   1.310  
   1.311          // Perturbation/restart
   1.312 -        if (delta_based_restart) {
   1.313 +        restart++;
   1.314 +        if (_delta_based_restart) {
   1.315            restart_nodes.clear();
   1.316            for (int i = 0; i != _n; i++) {
   1.317 -            if (_delta[i] >= restart_delta_limit)
   1.318 +            if (_delta[i] >= _restart_delta_limit)
   1.319                restart_nodes.push_back(i);
   1.320            }
   1.321          }
   1.322 @@ -663,12 +823,12 @@
   1.323          if (_size > _best_size) {
   1.324            _best_clique = _clique;
   1.325            _best_size = _size;
   1.326 -          if (_best_size == _n) return _best_size;
   1.327 +          if (_best_size >= max_size) return SIZE_LIMIT;
   1.328          }
   1.329          sel_method.update();
   1.330        }
   1.331  
   1.332 -      return _best_size;
   1.333 +      return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
   1.334      }
   1.335  
   1.336    }; //class GrossoLocatelliPullanMc