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