COIN-OR::LEMON - Graph Library

source: lemon/lemon/grosso_locatelli_pullan_mc.h @ 1270:dceba191c00d

Last change on this file since 1270:dceba191c00d was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

File size: 24.7 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2013
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#ifndef LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
20#define LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
21
22/// \ingroup approx_algs
23///
24/// \file
25/// \brief The iterated local search algorithm of Grosso, Locatelli, and Pullan
26/// for the maximum clique problem
27
28#include <vector>
29#include <limits>
30#include <lemon/core.h>
31#include <lemon/random.h>
32
33namespace lemon {
34
35  /// \addtogroup approx_algs
36  /// @{
37
38  /// \brief Implementation of the iterated local search algorithm of Grosso,
39  /// Locatelli, and Pullan for the maximum clique problem
40  ///
41  /// \ref GrossoLocatelliPullanMc implements the iterated local search
42  /// algorithm of Grosso, Locatelli, and Pullan for solving the \e maximum
43  /// \e clique \e problem \cite grosso08maxclique.
44  /// It is to find the largest complete subgraph (\e clique) in an
45  /// undirected graph, i.e., the largest set of nodes where each
46  /// pair of nodes is connected.
47  ///
48  /// This class provides a simple but highly efficient and robust heuristic
49  /// method that quickly finds a quite large clique, but not necessarily the
50  /// largest one.
51  /// The algorithm performs a certain number of iterations to find several
52  /// cliques and selects the largest one among them. Various limits can be
53  /// specified to control the running time and the effectiveness of the
54  /// search process.
55  ///
56  /// \tparam GR The undirected graph type the algorithm runs on.
57  ///
58  /// \note %GrossoLocatelliPullanMc provides three different node selection
59  /// rules, from which the most powerful one is used by default.
60  /// For more information, see \ref SelectionRule.
61  template <typename GR>
62  class GrossoLocatelliPullanMc
63  {
64  public:
65
66    /// \brief Constants for specifying the node selection rule.
67    ///
68    /// Enum type containing constants for specifying the node selection rule
69    /// for the \ref run() function.
70    ///
71    /// During the algorithm, nodes are selected for addition to the current
72    /// clique according to the applied rule.
73    /// In general, the PENALTY_BASED rule turned out to be the most powerful
74    /// and the most robust, thus it is the default option.
75    /// However, another selection rule can be specified using the \ref run()
76    /// function with the proper parameter.
77    enum SelectionRule {
78
79      /// A node is selected randomly without any evaluation at each step.
80      RANDOM,
81
82      /// A node of maximum degree is selected randomly at each step.
83      DEGREE_BASED,
84
85      /// A node of minimum penalty is selected randomly at each step.
86      /// The node penalties are updated adaptively after each stage of the
87      /// search process.
88      PENALTY_BASED
89    };
90
91    /// \brief Constants for the causes of search termination.
92    ///
93    /// Enum type containing constants for the different causes of search
94    /// termination. The \ref run() function returns one of these values.
95    enum TerminationCause {
96
97      /// The iteration count limit is reached.
98      ITERATION_LIMIT,
99
100      /// The step count limit is reached.
101      STEP_LIMIT,
102
103      /// The clique size limit is reached.
104      SIZE_LIMIT
105    };
106
107  private:
108
109    TEMPLATE_GRAPH_TYPEDEFS(GR);
110
111    typedef std::vector<int> IntVector;
112    typedef std::vector<char> BoolVector;
113    typedef std::vector<BoolVector> BoolMatrix;
114    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
115
116    // The underlying graph
117    const GR &_graph;
118    IntNodeMap _id;
119
120    // Internal matrix representation of the graph
121    BoolMatrix _gr;
122    int _n;
123
124    // Search options
125    bool _delta_based_restart;
126    int _restart_delta_limit;
127
128    // Search limits
129    int _iteration_limit;
130    int _step_limit;
131    int _size_limit;
132
133    // The current clique
134    BoolVector _clique;
135    int _size;
136
137    // The best clique found so far
138    BoolVector _best_clique;
139    int _best_size;
140
141    // The "distances" of the nodes from the current clique.
142    // _delta[u] is the number of nodes in the clique that are
143    // not connected with u.
144    IntVector _delta;
145
146    // The current tabu set
147    BoolVector _tabu;
148
149    // Random number generator
150    Random _rnd;
151
152  private:
153
154    // Implementation of the RANDOM node selection rule.
155    class RandomSelectionRule
156    {
157    private:
158
159      // References to the algorithm instance
160      const BoolVector &_clique;
161      const IntVector  &_delta;
162      const BoolVector &_tabu;
163      Random &_rnd;
164
165      // Pivot rule data
166      int _n;
167
168    public:
169
170      // Constructor
171      RandomSelectionRule(GrossoLocatelliPullanMc &mc) :
172        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
173        _rnd(mc._rnd), _n(mc._n)
174      {}
175
176      // Return a node index for a feasible add move or -1 if no one exists
177      int nextFeasibleAddNode() const {
178        int start_node = _rnd[_n];
179        for (int i = start_node; i != _n; i++) {
180          if (_delta[i] == 0 && !_tabu[i]) return i;
181        }
182        for (int i = 0; i != start_node; i++) {
183          if (_delta[i] == 0 && !_tabu[i]) return i;
184        }
185        return -1;
186      }
187
188      // Return a node index for a feasible swap move or -1 if no one exists
189      int nextFeasibleSwapNode() const {
190        int start_node = _rnd[_n];
191        for (int i = start_node; i != _n; i++) {
192          if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
193        }
194        for (int i = 0; i != start_node; i++) {
195          if (!_clique[i] && _delta[i] == 1 && !_tabu[i]) return i;
196        }
197        return -1;
198      }
199
200      // Return a node index for an add move or -1 if no one exists
201      int nextAddNode() const {
202        int start_node = _rnd[_n];
203        for (int i = start_node; i != _n; i++) {
204          if (_delta[i] == 0) return i;
205        }
206        for (int i = 0; i != start_node; i++) {
207          if (_delta[i] == 0) return i;
208        }
209        return -1;
210      }
211
212      // Update internal data structures between stages (if necessary)
213      void update() {}
214
215    }; //class RandomSelectionRule
216
217
218    // Implementation of the DEGREE_BASED node selection rule.
219    class DegreeBasedSelectionRule
220    {
221    private:
222
223      // References to the algorithm instance
224      const BoolVector &_clique;
225      const IntVector  &_delta;
226      const BoolVector &_tabu;
227      Random &_rnd;
228
229      // Pivot rule data
230      int _n;
231      IntVector _deg;
232
233    public:
234
235      // Constructor
236      DegreeBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
237        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
238        _rnd(mc._rnd), _n(mc._n), _deg(_n)
239      {
240        for (int i = 0; i != _n; i++) {
241          int d = 0;
242          BoolVector &row = mc._gr[i];
243          for (int j = 0; j != _n; j++) {
244            if (row[j]) d++;
245          }
246          _deg[i] = d;
247        }
248      }
249
250      // Return a node index for a feasible add move or -1 if no one exists
251      int nextFeasibleAddNode() const {
252        int start_node = _rnd[_n];
253        int node = -1, max_deg = -1;
254        for (int i = start_node; i != _n; i++) {
255          if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
256            node = i;
257            max_deg = _deg[i];
258          }
259        }
260        for (int i = 0; i != start_node; i++) {
261          if (_delta[i] == 0 && !_tabu[i] && _deg[i] > max_deg) {
262            node = i;
263            max_deg = _deg[i];
264          }
265        }
266        return node;
267      }
268
269      // Return a node index for a feasible swap move or -1 if no one exists
270      int nextFeasibleSwapNode() const {
271        int start_node = _rnd[_n];
272        int node = -1, max_deg = -1;
273        for (int i = start_node; i != _n; i++) {
274          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
275              _deg[i] > max_deg) {
276            node = i;
277            max_deg = _deg[i];
278          }
279        }
280        for (int i = 0; i != start_node; i++) {
281          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
282              _deg[i] > max_deg) {
283            node = i;
284            max_deg = _deg[i];
285          }
286        }
287        return node;
288      }
289
290      // Return a node index for an add move or -1 if no one exists
291      int nextAddNode() const {
292        int start_node = _rnd[_n];
293        int node = -1, max_deg = -1;
294        for (int i = start_node; i != _n; i++) {
295          if (_delta[i] == 0 && _deg[i] > max_deg) {
296            node = i;
297            max_deg = _deg[i];
298          }
299        }
300        for (int i = 0; i != start_node; i++) {
301          if (_delta[i] == 0 && _deg[i] > max_deg) {
302            node = i;
303            max_deg = _deg[i];
304          }
305        }
306        return node;
307      }
308
309      // Update internal data structures between stages (if necessary)
310      void update() {}
311
312    }; //class DegreeBasedSelectionRule
313
314
315    // Implementation of the PENALTY_BASED node selection rule.
316    class PenaltyBasedSelectionRule
317    {
318    private:
319
320      // References to the algorithm instance
321      const BoolVector &_clique;
322      const IntVector  &_delta;
323      const BoolVector &_tabu;
324      Random &_rnd;
325
326      // Pivot rule data
327      int _n;
328      IntVector _penalty;
329
330    public:
331
332      // Constructor
333      PenaltyBasedSelectionRule(GrossoLocatelliPullanMc &mc) :
334        _clique(mc._clique), _delta(mc._delta), _tabu(mc._tabu),
335        _rnd(mc._rnd), _n(mc._n), _penalty(_n, 0)
336      {}
337
338      // Return a node index for a feasible add move or -1 if no one exists
339      int nextFeasibleAddNode() const {
340        int start_node = _rnd[_n];
341        int node = -1, min_p = std::numeric_limits<int>::max();
342        for (int i = start_node; i != _n; i++) {
343          if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
344            node = i;
345            min_p = _penalty[i];
346          }
347        }
348        for (int i = 0; i != start_node; i++) {
349          if (_delta[i] == 0 && !_tabu[i] && _penalty[i] < min_p) {
350            node = i;
351            min_p = _penalty[i];
352          }
353        }
354        return node;
355      }
356
357      // Return a node index for a feasible swap move or -1 if no one exists
358      int nextFeasibleSwapNode() const {
359        int start_node = _rnd[_n];
360        int node = -1, min_p = std::numeric_limits<int>::max();
361        for (int i = start_node; i != _n; i++) {
362          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
363              _penalty[i] < min_p) {
364            node = i;
365            min_p = _penalty[i];
366          }
367        }
368        for (int i = 0; i != start_node; i++) {
369          if (!_clique[i] && _delta[i] == 1 && !_tabu[i] &&
370              _penalty[i] < min_p) {
371            node = i;
372            min_p = _penalty[i];
373          }
374        }
375        return node;
376      }
377
378      // Return a node index for an add move or -1 if no one exists
379      int nextAddNode() const {
380        int start_node = _rnd[_n];
381        int node = -1, min_p = std::numeric_limits<int>::max();
382        for (int i = start_node; i != _n; i++) {
383          if (_delta[i] == 0 && _penalty[i] < min_p) {
384            node = i;
385            min_p = _penalty[i];
386          }
387        }
388        for (int i = 0; i != start_node; i++) {
389          if (_delta[i] == 0 && _penalty[i] < min_p) {
390            node = i;
391            min_p = _penalty[i];
392          }
393        }
394        return node;
395      }
396
397      // Update internal data structures between stages (if necessary)
398      void update() {}
399
400    }; //class PenaltyBasedSelectionRule
401
402  public:
403
404    /// \brief Constructor.
405    ///
406    /// Constructor.
407    /// The global \ref rnd "random number generator instance" is used
408    /// during the algorithm.
409    ///
410    /// \param graph The undirected graph the algorithm runs on.
411    GrossoLocatelliPullanMc(const GR& graph) :
412      _graph(graph), _id(_graph), _rnd(rnd)
413    {
414      initOptions();
415    }
416
417    /// \brief Constructor with random seed.
418    ///
419    /// Constructor with random seed.
420    ///
421    /// \param graph The undirected graph the algorithm runs on.
422    /// \param seed Seed value for the internal random number generator
423    /// that is used during the algorithm.
424    GrossoLocatelliPullanMc(const GR& graph, int seed) :
425      _graph(graph), _id(_graph), _rnd(seed)
426    {
427      initOptions();
428    }
429
430    /// \brief Constructor with random number generator.
431    ///
432    /// Constructor with random number generator.
433    ///
434    /// \param graph The undirected graph the algorithm runs on.
435    /// \param random A random number generator that is used during the
436    /// algorithm.
437    GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
438      _graph(graph), _id(_graph), _rnd(random)
439    {
440      initOptions();
441    }
442
443    /// \name Execution Control
444    /// The \ref run() function can be used to execute the algorithm.\n
445    /// The functions \ref iterationLimit(int), \ref stepLimit(int), and
446    /// \ref sizeLimit(int) can be used to specify various limits for the
447    /// search process.
448
449    /// @{
450
451    /// \brief Sets the maximum number of iterations.
452    ///
453    /// This function sets the maximum number of iterations.
454    /// Each iteration of the algorithm finds a maximal clique (but not
455    /// necessarily the largest one) by performing several search steps
456    /// (node selections).
457    ///
458    /// This limit controls the running time and the success of the
459    /// algorithm. For larger values, the algorithm runs slower, but it more
460    /// likely finds larger cliques. For smaller values, the algorithm is
461    /// faster but probably gives worse results.
462    ///
463    /// The default value is \c 1000.
464    /// \c -1 means that number of iterations is not limited.
465    ///
466    /// \warning You should specify a reasonable limit for the number of
467    /// iterations and/or the number of search steps.
468    ///
469    /// \return <tt>(*this)</tt>
470    ///
471    /// \sa stepLimit(int)
472    /// \sa sizeLimit(int)
473    GrossoLocatelliPullanMc& iterationLimit(int limit) {
474      _iteration_limit = limit;
475      return *this;
476    }
477
478    /// \brief Sets the maximum number of search steps.
479    ///
480    /// This function sets the maximum number of elementary search steps.
481    /// Each iteration of the algorithm finds a maximal clique (but not
482    /// necessarily the largest one) by performing several search steps
483    /// (node selections).
484    ///
485    /// This limit controls the running time and the success of the
486    /// algorithm. For larger values, the algorithm runs slower, but it more
487    /// likely finds larger cliques. For smaller values, the algorithm is
488    /// faster but probably gives worse results.
489    ///
490    /// The default value is \c -1, which means that number of steps
491    /// is not limited explicitly. However, the number of iterations is
492    /// limited and each iteration performs a finite number of search steps.
493    ///
494    /// \warning You should specify a reasonable limit for the number of
495    /// iterations and/or the number of search steps.
496    ///
497    /// \return <tt>(*this)</tt>
498    ///
499    /// \sa iterationLimit(int)
500    /// \sa sizeLimit(int)
501    GrossoLocatelliPullanMc& stepLimit(int limit) {
502      _step_limit = limit;
503      return *this;
504    }
505
506    /// \brief Sets the desired clique size.
507    ///
508    /// This function sets the desired clique size that serves as a search
509    /// limit. If a clique of this size (or a larger one) is found, then the
510    /// algorithm terminates.
511    ///
512    /// This function is especially useful if you know an exact upper bound
513    /// for the size of the cliques in the graph or if any clique above
514    /// a certain size limit is sufficient for your application.
515    ///
516    /// The default value is \c -1, which means that the size limit is set to
517    /// the number of nodes in the graph.
518    ///
519    /// \return <tt>(*this)</tt>
520    ///
521    /// \sa iterationLimit(int)
522    /// \sa stepLimit(int)
523    GrossoLocatelliPullanMc& sizeLimit(int limit) {
524      _size_limit = limit;
525      return *this;
526    }
527
528    /// \brief The maximum number of iterations.
529    ///
530    /// This function gives back the maximum number of iterations.
531    /// \c -1 means that no limit is specified.
532    ///
533    /// \sa iterationLimit(int)
534    int iterationLimit() const {
535      return _iteration_limit;
536    }
537
538    /// \brief The maximum number of search steps.
539    ///
540    /// This function gives back the maximum number of search steps.
541    /// \c -1 means that no limit is specified.
542    ///
543    /// \sa stepLimit(int)
544    int stepLimit() const {
545      return _step_limit;
546    }
547
548    /// \brief The desired clique size.
549    ///
550    /// This function gives back the desired clique size that serves as a
551    /// search limit. \c -1 means that this limit is set to the number of
552    /// nodes in the graph.
553    ///
554    /// \sa sizeLimit(int)
555    int sizeLimit() const {
556      return _size_limit;
557    }
558
559    /// \brief Runs the algorithm.
560    ///
561    /// This function runs the algorithm. If one of the specified limits
562    /// is reached, the search process terminates.
563    ///
564    /// \param rule The node selection rule. For more information, see
565    /// \ref SelectionRule.
566    ///
567    /// \return The termination cause of the search. For more information,
568    /// see \ref TerminationCause.
569    TerminationCause run(SelectionRule rule = PENALTY_BASED)
570    {
571      init();
572      switch (rule) {
573        case RANDOM:
574          return start<RandomSelectionRule>();
575        case DEGREE_BASED:
576          return start<DegreeBasedSelectionRule>();
577        default:
578          return start<PenaltyBasedSelectionRule>();
579      }
580    }
581
582    /// @}
583
584    /// \name Query Functions
585    /// The results of the algorithm can be obtained using these functions.\n
586    /// The run() function must be called before using them.
587
588    /// @{
589
590    /// \brief The size of the found clique
591    ///
592    /// This function returns the size of the found clique.
593    ///
594    /// \pre run() must be called before using this function.
595    int cliqueSize() const {
596      return _best_size;
597    }
598
599    /// \brief Gives back the found clique in a \c bool node map
600    ///
601    /// This function gives back the characteristic vector of the found
602    /// clique in the given node map.
603    /// It must be a \ref concepts::WriteMap "writable" node map with
604    /// \c bool (or convertible) value type.
605    ///
606    /// \pre run() must be called before using this function.
607    template <typename CliqueMap>
608    void cliqueMap(CliqueMap &map) const {
609      for (NodeIt n(_graph); n != INVALID; ++n) {
610        map[n] = static_cast<bool>(_best_clique[_id[n]]);
611      }
612    }
613
614    /// \brief Iterator to list the nodes of the found clique
615    ///
616    /// This iterator class lists the nodes of the found clique.
617    /// Before using it, you must allocate a GrossoLocatelliPullanMc instance
618    /// and call its \ref GrossoLocatelliPullanMc::run() "run()" method.
619    ///
620    /// The following example prints out the IDs of the nodes in the found
621    /// clique.
622    /// \code
623    ///   GrossoLocatelliPullanMc<Graph> mc(g);
624    ///   mc.run();
625    ///   for (GrossoLocatelliPullanMc<Graph>::CliqueNodeIt n(mc);
626    ///        n != INVALID; ++n)
627    ///   {
628    ///     std::cout << g.id(n) << std::endl;
629    ///   }
630    /// \endcode
631    class CliqueNodeIt
632    {
633    private:
634      NodeIt _it;
635      BoolNodeMap _map;
636
637    public:
638
639      /// Constructor
640
641      /// Constructor.
642      /// \param mc The algorithm instance.
643      CliqueNodeIt(const GrossoLocatelliPullanMc &mc)
644       : _map(mc._graph)
645      {
646        mc.cliqueMap(_map);
647        for (_it = NodeIt(mc._graph); _it != INVALID && !_map[_it]; ++_it) ;
648      }
649
650      /// Conversion to \c Node
651      operator Node() const { return _it; }
652
653      bool operator==(Invalid) const { return _it == INVALID; }
654      bool operator!=(Invalid) const { return _it != INVALID; }
655
656      /// Next node
657      CliqueNodeIt &operator++() {
658        for (++_it; _it != INVALID && !_map[_it]; ++_it) ;
659        return *this;
660      }
661
662      /// Postfix incrementation
663
664      /// Postfix incrementation.
665      ///
666      /// \warning This incrementation returns a \c Node, not a
667      /// \c CliqueNodeIt as one may expect.
668      typename GR::Node operator++(int) {
669        Node n=*this;
670        ++(*this);
671        return n;
672      }
673
674    };
675
676    /// @}
677
678  private:
679
680    // Initialize search options and limits
681    void initOptions() {
682      // Search options
683      _delta_based_restart = true;
684      _restart_delta_limit = 4;
685
686      // Search limits
687      _iteration_limit = 1000;
688      _step_limit = -1;             // this is disabled by default
689      _size_limit = -1;             // this is disabled by default
690    }
691
692    // Adds a node to the current clique
693    void addCliqueNode(int u) {
694      if (_clique[u]) return;
695      _clique[u] = true;
696      _size++;
697      BoolVector &row = _gr[u];
698      for (int i = 0; i != _n; i++) {
699        if (!row[i]) _delta[i]++;
700      }
701    }
702
703    // Removes a node from the current clique
704    void delCliqueNode(int u) {
705      if (!_clique[u]) return;
706      _clique[u] = false;
707      _size--;
708      BoolVector &row = _gr[u];
709      for (int i = 0; i != _n; i++) {
710        if (!row[i]) _delta[i]--;
711      }
712    }
713
714    // Initialize data structures
715    void init() {
716      _n = countNodes(_graph);
717      int ui = 0;
718      for (NodeIt u(_graph); u != INVALID; ++u) {
719        _id[u] = ui++;
720      }
721      _gr.clear();
722      _gr.resize(_n, BoolVector(_n, false));
723      ui = 0;
724      for (NodeIt u(_graph); u != INVALID; ++u) {
725        for (IncEdgeIt e(_graph, u); e != INVALID; ++e) {
726          int vi = _id[_graph.runningNode(e)];
727          _gr[ui][vi] = true;
728          _gr[vi][ui] = true;
729        }
730        ++ui;
731      }
732
733      _clique.clear();
734      _clique.resize(_n, false);
735      _size = 0;
736      _best_clique.clear();
737      _best_clique.resize(_n, false);
738      _best_size = 0;
739      _delta.clear();
740      _delta.resize(_n, 0);
741      _tabu.clear();
742      _tabu.resize(_n, false);
743    }
744
745    // Executes the algorithm
746    template <typename SelectionRuleImpl>
747    TerminationCause start() {
748      if (_n == 0) return SIZE_LIMIT;
749      if (_n == 1) {
750        _best_clique[0] = true;
751        _best_size = 1;
752        return SIZE_LIMIT;
753      }
754
755      // Iterated local search algorithm
756      const int max_size = _size_limit >= 0 ? _size_limit : _n;
757      const int max_restart = _iteration_limit >= 0 ?
758        _iteration_limit : std::numeric_limits<int>::max();
759      const int max_select = _step_limit >= 0 ?
760        _step_limit : std::numeric_limits<int>::max();
761
762      SelectionRuleImpl sel_method(*this);
763      int select = 0, restart = 0;
764      IntVector restart_nodes;
765      while (select < max_select && restart < max_restart) {
766
767        // Perturbation/restart
768        restart++;
769        if (_delta_based_restart) {
770          restart_nodes.clear();
771          for (int i = 0; i != _n; i++) {
772            if (_delta[i] >= _restart_delta_limit)
773              restart_nodes.push_back(i);
774          }
775        }
776        int rs_node = -1;
777        if (restart_nodes.size() > 0) {
778          rs_node = restart_nodes[_rnd[restart_nodes.size()]];
779        } else {
780          rs_node = _rnd[_n];
781        }
782        BoolVector &row = _gr[rs_node];
783        for (int i = 0; i != _n; i++) {
784          if (_clique[i] && !row[i]) delCliqueNode(i);
785        }
786        addCliqueNode(rs_node);
787
788        // Local search
789        _tabu.clear();
790        _tabu.resize(_n, false);
791        bool tabu_empty = true;
792        int max_swap = _size;
793        while (select < max_select) {
794          select++;
795          int u;
796          if ((u = sel_method.nextFeasibleAddNode()) != -1) {
797            // Feasible add move
798            addCliqueNode(u);
799            if (tabu_empty) max_swap = _size;
800          }
801          else if ((u = sel_method.nextFeasibleSwapNode()) != -1) {
802            // Feasible swap move
803            int v = -1;
804            BoolVector &row = _gr[u];
805            for (int i = 0; i != _n; i++) {
806              if (_clique[i] && !row[i]) {
807                v = i;
808                break;
809              }
810            }
811            addCliqueNode(u);
812            delCliqueNode(v);
813            _tabu[v] = true;
814            tabu_empty = false;
815            if (--max_swap <= 0) break;
816          }
817          else if ((u = sel_method.nextAddNode()) != -1) {
818            // Non-feasible add move
819            addCliqueNode(u);
820          }
821          else break;
822        }
823        if (_size > _best_size) {
824          _best_clique = _clique;
825          _best_size = _size;
826          if (_best_size >= max_size) return SIZE_LIMIT;
827        }
828        sel_method.update();
829      }
830
831      return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
832    }
833
834  }; //class GrossoLocatelliPullanMc
835
836  ///@}
837
838} //namespace lemon
839
840#endif //LEMON_GROSSO_LOCATELLI_PULLAN_MC_H
Note: See TracBrowser for help on using the repository browser.