COIN-OR::LEMON - Graph Library

Changeset 1022:8583fb74238c in lemon


Ignore:
Timestamp:
01/08/11 15:52:07 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Various search limits for the max clique alg (#405)

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/grosso_locatelli_pullan_mc.h

    r999 r1022  
    4747  ///
    4848  /// This class provides a simple but highly efficient and robust heuristic
    49   /// method that quickly finds a large clique, but not necessarily the
     49  /// method that quickly finds a quite large clique, but not necessarily the
    5050  /// 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.
    5155  ///
    5256  /// \tparam GR The undirected graph type the algorithm runs on.
     
    8589    };
    8690
     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
    87107  private:
    88108
     
    94114    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    95115
     116    // The underlying graph
    96117    const GR &_graph;
    97118    IntNodeMap _id;
     
    100121    BoolMatrix _gr;
    101122    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;
    102132
    103133    // The current clique
     
    381411    GrossoLocatelliPullanMc(const GR& graph) :
    382412      _graph(graph), _id(_graph), _rnd(rnd)
    383     {}
     413    {
     414      initOptions();
     415    }
    384416
    385417    /// \brief Constructor with random seed.
     
    392424    GrossoLocatelliPullanMc(const GR& graph, int seed) :
    393425      _graph(graph), _id(_graph), _rnd(seed)
    394     {}
     426    {
     427      initOptions();
     428    }
    395429
    396430    /// \brief Constructor with random number generator.
     
    403437    GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
    404438      _graph(graph), _id(_graph), _rnd(random)
    405     {}
     439    {
     440      initOptions();
     441    }
    406442
    407443    /// \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   
    408449    /// @{
    409 
    410     /// \brief Runs the algorithm.
    411     ///
    412     /// This function runs the algorithm.
    413     ///
    414     /// \param step_num The maximum number of node selections (steps)
    415     /// during the search process.
    416     /// This parameter controls the running time and the success of the
    417     /// algorithm. For larger values, the algorithm runs slower but it more
     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
    418460    /// likely finds larger cliques. For smaller values, the algorithm is
    419461    /// 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    ///
    420564    /// \param rule The node selection rule. For more information, see
    421565    /// \ref SelectionRule.
    422566    ///
    423     /// \return The size of the found clique.
    424     int run(int step_num = 100000,
    425             SelectionRule rule = PENALTY_BASED)
     567    /// \return The termination cause of the search. For more information,
     568    /// see \ref TerminationCause.
     569    TerminationCause run(SelectionRule rule = PENALTY_BASED)
    426570    {
    427571      init();
    428572      switch (rule) {
    429573        case RANDOM:
    430           return start<RandomSelectionRule>(step_num);
     574          return start<RandomSelectionRule>();
    431575        case DEGREE_BASED:
    432           return start<DegreeBasedSelectionRule>(step_num);
    433         case PENALTY_BASED:
    434           return start<PenaltyBasedSelectionRule>(step_num);
    435       }
    436       return 0; // avoid warning
     576          return start<DegreeBasedSelectionRule>();
     577        default:
     578          return start<PenaltyBasedSelectionRule>();
     579      }
    437580    }
    438581
     
    440583
    441584    /// \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
    442588    /// @{
    443589
     
    531677
    532678  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    }
    533691
    534692    // Adds a node to the current clique
     
    587745    // Executes the algorithm
    588746    template <typename SelectionRuleImpl>
    589     int start(int max_select) {
    590       // Options for the restart rule
    591       const bool delta_based_restart = true;
    592       const int restart_delta_limit = 4;
    593 
    594       if (_n == 0) return 0;
     747    TerminationCause start() {
     748      if (_n == 0) return SIZE_LIMIT;
    595749      if (_n == 1) {
    596750        _best_clique[0] = true;
    597751        _best_size = 1;
    598         return _best_size;
    599       }
    600 
    601       // Iterated local search
     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
    602762      SelectionRuleImpl sel_method(*this);
    603       int select = 0;
     763      int select = 0, restart = 0;
    604764      IntVector restart_nodes;
    605 
    606       while (select < max_select) {
     765      while (select < max_select && restart < max_restart) {
    607766
    608767        // Perturbation/restart
    609         if (delta_based_restart) {
     768        restart++;
     769        if (_delta_based_restart) {
    610770          restart_nodes.clear();
    611771          for (int i = 0; i != _n; i++) {
    612             if (_delta[i] >= restart_delta_limit)
     772            if (_delta[i] >= _restart_delta_limit)
    613773              restart_nodes.push_back(i);
    614774          }
     
    664824          _best_clique = _clique;
    665825          _best_size = _size;
    666           if (_best_size == _n) return _best_size;
     826          if (_best_size >= max_size) return SIZE_LIMIT;
    667827        }
    668828        sel_method.update();
    669829      }
    670830
    671       return _best_size;
     831      return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
    672832    }
    673833
  • test/max_clique_test.cc

    r999 r1022  
    5959// Check with general graphs
    6060template <typename Param>
    61 void checkMaxCliqueGeneral(int max_sel, Param rule) {
     61void checkMaxCliqueGeneral(Param rule) {
    6262  typedef ListGraph GR;
    6363  typedef GrossoLocatelliPullanMc<GR> McAlg;
     
    6969    GR::NodeMap<bool> map(g);
    7070    McAlg mc(g);
    71     check(mc.run(max_sel, rule) == 0, "Wrong clique size");
     71    mc.iterationLimit(50);
     72    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
    7273    check(mc.cliqueSize() == 0, "Wrong clique size");
    7374    check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
    7475
    7576    GR::Node u = g.addNode();
    76     check(mc.run(max_sel, rule) == 1, "Wrong clique size");
     77    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
    7778    check(mc.cliqueSize() == 1, "Wrong clique size");
    7879    mc.cliqueMap(map);
     
    8384   
    8485    GR::Node v = g.addNode();
    85     check(mc.run(max_sel, rule) == 1, "Wrong clique size");
     86    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
    8687    check(mc.cliqueSize() == 1, "Wrong clique size");
    8788    mc.cliqueMap(map);
     
    9192
    9293    g.addEdge(u, v);
    93     check(mc.run(max_sel, rule) == 2, "Wrong clique size");
     94    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
    9495    check(mc.cliqueSize() == 2, "Wrong clique size");
    9596    mc.cliqueMap(map);
     
    111112   
    112113    McAlg mc(g);
    113     check(mc.run(max_sel, rule) == 4, "Wrong clique size");
     114    mc.iterationLimit(50);
     115    check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
    114116    check(mc.cliqueSize() == 4, "Wrong clique size");
    115117    mc.cliqueMap(map);
     
    128130// Check with full graphs
    129131template <typename Param>
    130 void checkMaxCliqueFullGraph(int max_sel, Param rule) {
     132void checkMaxCliqueFullGraph(Param rule) {
    131133  typedef FullGraph GR;
    132134  typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
     
    137139    GR::NodeMap<bool> map(g);
    138140    McAlg mc(g);
    139     check(mc.run(max_sel, rule) == size, "Wrong clique size");
     141    check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
    140142    check(mc.cliqueSize() == size, "Wrong clique size");
    141143    mc.cliqueMap(map);
     
    151153// Check with grid graphs
    152154template <typename Param>
    153 void checkMaxCliqueGridGraph(int max_sel, Param rule) {
     155void checkMaxCliqueGridGraph(Param rule) {
    154156  GridGraph g(5, 7);
    155157  GridGraph::NodeMap<char> map(g);
    156158  GrossoLocatelliPullanMc<GridGraph> mc(g);
    157   check(mc.run(max_sel, rule) == 2, "Wrong clique size");
     159 
     160  mc.iterationLimit(100);
     161  check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause");
     162  check(mc.cliqueSize() == 2, "Wrong clique size");
     163
     164  mc.stepLimit(100);
     165  check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause");
     166  check(mc.cliqueSize() == 2, "Wrong clique size");
     167
     168  mc.sizeLimit(2);
     169  check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause");
    158170  check(mc.cliqueSize() == 2, "Wrong clique size");
    159171}
     
    161173
    162174int main() {
    163   checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::RANDOM);
    164   checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
    165   checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
     175  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
     176  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
     177  checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
    166178
    167   checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
    168   checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
    169   checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
     179  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
     180  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
     181  checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
    170182                       
    171   checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
    172   checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
    173   checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
     183  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
     184  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
     185  checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
    174186                       
    175187  return 0;
Note: See TracChangeset for help on using the changeset viewer.