lemon/grosso_locatelli_pullan_mc.h
changeset 1047 f7247b5c04bf
parent 904 c279b19abc62
child 1053 1c978b5bcc65
equal deleted inserted replaced
0:1f985e41fbeb 1:5933ad89f2dd
    44   /// It is to find the largest complete subgraph (\e clique) in an
    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
    45   /// undirected graph, i.e., the largest set of nodes where each
    46   /// pair of nodes is connected.
    46   /// pair of nodes is connected.
    47   ///
    47   ///
    48   /// This class provides a simple but highly efficient and robust heuristic
    48   /// 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
    50   /// largest one.
    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.
    51   ///
    55   ///
    52   /// \tparam GR The undirected graph type the algorithm runs on.
    56   /// \tparam GR The undirected graph type the algorithm runs on.
    53   ///
    57   ///
    54   /// \note %GrossoLocatelliPullanMc provides three different node selection
    58   /// \note %GrossoLocatelliPullanMc provides three different node selection
    55   /// rules, from which the most powerful one is used by default.
    59   /// rules, from which the most powerful one is used by default.
    82       /// The node penalties are updated adaptively after each stage of the
    86       /// The node penalties are updated adaptively after each stage of the
    83       /// search process.
    87       /// search process.
    84       PENALTY_BASED
    88       PENALTY_BASED
    85     };
    89     };
    86 
    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 
    87   private:
   107   private:
    88 
   108 
    89     TEMPLATE_GRAPH_TYPEDEFS(GR);
   109     TEMPLATE_GRAPH_TYPEDEFS(GR);
    90 
   110 
    91     typedef std::vector<int> IntVector;
   111     typedef std::vector<int> IntVector;
    92     typedef std::vector<char> BoolVector;
   112     typedef std::vector<char> BoolVector;
    93     typedef std::vector<BoolVector> BoolMatrix;
   113     typedef std::vector<BoolVector> BoolMatrix;
    94     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
   114     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    95 
   115 
       
   116     // The underlying graph
    96     const GR &_graph;
   117     const GR &_graph;
    97     IntNodeMap _id;
   118     IntNodeMap _id;
    98 
   119 
    99     // Internal matrix representation of the graph
   120     // Internal matrix representation of the graph
   100     BoolMatrix _gr;
   121     BoolMatrix _gr;
   101     int _n;
   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;
   102 
   132 
   103     // The current clique
   133     // The current clique
   104     BoolVector _clique;
   134     BoolVector _clique;
   105     int _size;
   135     int _size;
   106 
   136 
   378     /// during the algorithm.
   408     /// during the algorithm.
   379     ///
   409     ///
   380     /// \param graph The undirected graph the algorithm runs on.
   410     /// \param graph The undirected graph the algorithm runs on.
   381     GrossoLocatelliPullanMc(const GR& graph) :
   411     GrossoLocatelliPullanMc(const GR& graph) :
   382       _graph(graph), _id(_graph), _rnd(rnd)
   412       _graph(graph), _id(_graph), _rnd(rnd)
   383     {}
   413     {
       
   414       initOptions();
       
   415     }
   384 
   416 
   385     /// \brief Constructor with random seed.
   417     /// \brief Constructor with random seed.
   386     ///
   418     ///
   387     /// Constructor with random seed.
   419     /// Constructor with random seed.
   388     ///
   420     ///
   389     /// \param graph The undirected graph the algorithm runs on.
   421     /// \param graph The undirected graph the algorithm runs on.
   390     /// \param seed Seed value for the internal random number generator
   422     /// \param seed Seed value for the internal random number generator
   391     /// that is used during the algorithm.
   423     /// that is used during the algorithm.
   392     GrossoLocatelliPullanMc(const GR& graph, int seed) :
   424     GrossoLocatelliPullanMc(const GR& graph, int seed) :
   393       _graph(graph), _id(_graph), _rnd(seed)
   425       _graph(graph), _id(_graph), _rnd(seed)
   394     {}
   426     {
       
   427       initOptions();
       
   428     }
   395 
   429 
   396     /// \brief Constructor with random number generator.
   430     /// \brief Constructor with random number generator.
   397     ///
   431     ///
   398     /// Constructor with random number generator.
   432     /// Constructor with random number generator.
   399     ///
   433     ///
   400     /// \param graph The undirected graph the algorithm runs on.
   434     /// \param graph The undirected graph the algorithm runs on.
   401     /// \param random A random number generator that is used during the
   435     /// \param random A random number generator that is used during the
   402     /// algorithm.
   436     /// algorithm.
   403     GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
   437     GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
   404       _graph(graph), _id(_graph), _rnd(random)
   438       _graph(graph), _id(_graph), _rnd(random)
   405     {}
   439     {
       
   440       initOptions();
       
   441     }
   406 
   442 
   407     /// \name Execution Control
   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     
   408     /// @{
   449     /// @{
   409 
   450     
   410     /// \brief Runs the algorithm.
   451     /// \brief Sets the maximum number of iterations.
   411     ///
   452     ///
   412     /// This function runs the algorithm.
   453     /// This function sets the maximum number of iterations.
   413     ///
   454     /// Each iteration of the algorithm finds a maximal clique (but not
   414     /// \param step_num The maximum number of node selections (steps)
   455     /// necessarily the largest one) by performing several search steps
   415     /// during the search process.
   456     /// (node selections).
   416     /// This parameter controls the running time and the success of the
   457     ///
   417     /// algorithm. For larger values, the algorithm runs slower but it more
   458     /// This limit controls the running time and the success of the
       
   459     /// algorithm. For larger values, the algorithm runs slower, but it more
   418     /// likely finds larger cliques. For smaller values, the algorithm is
   460     /// likely finds larger cliques. For smaller values, the algorithm is
   419     /// faster but probably gives worse results.
   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     ///
   420     /// \param rule The node selection rule. For more information, see
   564     /// \param rule The node selection rule. For more information, see
   421     /// \ref SelectionRule.
   565     /// \ref SelectionRule.
   422     ///
   566     ///
   423     /// \return The size of the found clique.
   567     /// \return The termination cause of the search. For more information,
   424     int run(int step_num = 100000,
   568     /// see \ref TerminationCause.
   425             SelectionRule rule = PENALTY_BASED)
   569     TerminationCause run(SelectionRule rule = PENALTY_BASED)
   426     {
   570     {
   427       init();
   571       init();
   428       switch (rule) {
   572       switch (rule) {
   429         case RANDOM:
   573         case RANDOM:
   430           return start<RandomSelectionRule>(step_num);
   574           return start<RandomSelectionRule>();
   431         case DEGREE_BASED:
   575         case DEGREE_BASED:
   432           return start<DegreeBasedSelectionRule>(step_num);
   576           return start<DegreeBasedSelectionRule>();
   433         case PENALTY_BASED:
   577         default:
   434           return start<PenaltyBasedSelectionRule>(step_num);
   578           return start<PenaltyBasedSelectionRule>();
   435       }
   579       }
   436       return 0; // avoid warning
       
   437     }
   580     }
   438 
   581 
   439     /// @}
   582     /// @}
   440 
   583 
   441     /// \name Query Functions
   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 
   442     /// @{
   588     /// @{
   443 
   589 
   444     /// \brief The size of the found clique
   590     /// \brief The size of the found clique
   445     ///
   591     ///
   446     /// This function returns the size of the found clique.
   592     /// This function returns the size of the found clique.
   528     };
   674     };
   529 
   675 
   530     /// @}
   676     /// @}
   531 
   677 
   532   private:
   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     }
   533 
   691 
   534     // Adds a node to the current clique
   692     // Adds a node to the current clique
   535     void addCliqueNode(int u) {
   693     void addCliqueNode(int u) {
   536       if (_clique[u]) return;
   694       if (_clique[u]) return;
   537       _clique[u] = true;
   695       _clique[u] = true;
   584       _tabu.resize(_n, false);
   742       _tabu.resize(_n, false);
   585     }
   743     }
   586 
   744 
   587     // Executes the algorithm
   745     // Executes the algorithm
   588     template <typename SelectionRuleImpl>
   746     template <typename SelectionRuleImpl>
   589     int start(int max_select) {
   747     TerminationCause start() {
   590       // Options for the restart rule
   748       if (_n == 0) return SIZE_LIMIT;
   591       const bool delta_based_restart = true;
       
   592       const int restart_delta_limit = 4;
       
   593 
       
   594       if (_n == 0) return 0;
       
   595       if (_n == 1) {
   749       if (_n == 1) {
   596         _best_clique[0] = true;
   750         _best_clique[0] = true;
   597         _best_size = 1;
   751         _best_size = 1;
   598         return _best_size;
   752         return SIZE_LIMIT;
   599       }
   753       }
   600 
   754 
   601       // Iterated local search
   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 
   602       SelectionRuleImpl sel_method(*this);
   762       SelectionRuleImpl sel_method(*this);
   603       int select = 0;
   763       int select = 0, restart = 0;
   604       IntVector restart_nodes;
   764       IntVector restart_nodes;
   605 
   765       while (select < max_select && restart < max_restart) {
   606       while (select < max_select) {
       
   607 
   766 
   608         // Perturbation/restart
   767         // Perturbation/restart
   609         if (delta_based_restart) {
   768         restart++;
       
   769         if (_delta_based_restart) {
   610           restart_nodes.clear();
   770           restart_nodes.clear();
   611           for (int i = 0; i != _n; i++) {
   771           for (int i = 0; i != _n; i++) {
   612             if (_delta[i] >= restart_delta_limit)
   772             if (_delta[i] >= _restart_delta_limit)
   613               restart_nodes.push_back(i);
   773               restart_nodes.push_back(i);
   614           }
   774           }
   615         }
   775         }
   616         int rs_node = -1;
   776         int rs_node = -1;
   617         if (restart_nodes.size() > 0) {
   777         if (restart_nodes.size() > 0) {
   661           else break;
   821           else break;
   662         }
   822         }
   663         if (_size > _best_size) {
   823         if (_size > _best_size) {
   664           _best_clique = _clique;
   824           _best_clique = _clique;
   665           _best_size = _size;
   825           _best_size = _size;
   666           if (_best_size == _n) return _best_size;
   826           if (_best_size >= max_size) return SIZE_LIMIT;
   667         }
   827         }
   668         sel_method.update();
   828         sel_method.update();
   669       }
   829       }
   670 
   830 
   671       return _best_size;
   831       return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
   672     }
   832     }
   673 
   833 
   674   }; //class GrossoLocatelliPullanMc
   834   }; //class GrossoLocatelliPullanMc
   675 
   835 
   676   ///@}
   836   ///@}