lemon-1.3: comparison lemon/grosso_locatelli_pullan

equal deleted inserted replaced

-:1f985e41fbeb
+:5933ad89f2dd
 /// It is to find the largest complete subgraph (\e clique) in an
 /// undirected graph, i.e., the largest set of nodes where each
 /// pair of nodes is connected.
 ///
 /// This class provides a simple but highly efficient and robust heuristic
-/// method that quickly finds a large clique, but not necessarily the
+/// method that quickly finds a quite large clique, but not necessarily the
 /// largest one.
+/// The algorithm performs a certain number of iterations to find several
+/// cliques and selects the largest one among them. Various limits can be
+/// specified to control the running time and the effectiveness of the
+/// search process.
 ///
 /// \tparam GR The undirected graph type the algorithm runs on.
 ///
 /// \note %GrossoLocatelliPullanMc provides three different node selection
 /// rules, from which the most powerful one is used by default.
 /// The node penalties are updated adaptively after each stage of the
 /// search process.
 PENALTY_BASED
 };
+/// \brief Constants for the causes of search termination.
+///
+/// Enum type containing constants for the different causes of search
+/// termination. The \ref run() function returns one of these values.
+enum TerminationCause {
+/// The iteration count limit is reached.
+ITERATION_LIMIT,
+/// The step count limit is reached.
+STEP_LIMIT,
+/// The clique size limit is reached.
+SIZE_LIMIT
+};
 private:
 TEMPLATE_GRAPH_TYPEDEFS(GR);
 typedef std::vector<int> IntVector;
 typedef std::vector<char> BoolVector;
 typedef std::vector<BoolVector> BoolMatrix;
 // Note: vector<char> is used instead of vector<bool> for efficiency reasons
+// The underlying graph
 const GR &_graph;
 IntNodeMap _id;
 // Internal matrix representation of the graph
 BoolMatrix _gr;
 int _n;
+// Search options
+bool _delta_based_restart;
+int _restart_delta_limit;
+// Search limits
+int _iteration_limit;
+int _step_limit;
+int _size_limit;
 // The current clique
 BoolVector _clique;
 int _size;
 /// during the algorithm.
 ///
 /// \param graph The undirected graph the algorithm runs on.
 GrossoLocatelliPullanMc(const GR& graph) :
 _graph(graph), _id(_graph), _rnd(rnd)
-{}
+{
+initOptions();
+}
 /// \brief Constructor with random seed.
 ///
 /// Constructor with random seed.
 ///
 /// \param graph The undirected graph the algorithm runs on.
 /// \param seed Seed value for the internal random number generator
 /// that is used during the algorithm.
 GrossoLocatelliPullanMc(const GR& graph, int seed) :
 _graph(graph), _id(_graph), _rnd(seed)
-{}
+{
+initOptions();
+}
 /// \brief Constructor with random number generator.
 ///
 /// Constructor with random number generator.
 ///
 /// \param graph The undirected graph the algorithm runs on.
 /// \param random A random number generator that is used during the
 /// algorithm.
 GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
 _graph(graph), _id(_graph), _rnd(random)
-{}
+{
+initOptions();
+}
 /// \name Execution Control
+/// The \ref run() function can be used to execute the algorithm.\n
+/// The functions \ref iterationLimit(int), \ref stepLimit(int), and
+/// \ref sizeLimit(int) can be used to specify various limits for the
+/// search process.
 /// @{
-/// \brief Runs the algorithm.
+/// \brief Sets the maximum number of iterations.
 ///
-/// This function runs the algorithm.
+/// This function sets the maximum number of iterations.
-///
+/// Each iteration of the algorithm finds a maximal clique (but not
-/// \param step_num The maximum number of node selections (steps)
+/// necessarily the largest one) by performing several search steps
-/// during the search process.
+/// (node selections).
-/// This parameter controls the running time and the success of the
+///
-/// algorithm. For larger values, the algorithm runs slower but it more
+/// This limit controls the running time and the success of the
+/// algorithm. For larger values, the algorithm runs slower, but it more
 /// likely finds larger cliques. For smaller values, the algorithm is
 /// faster but probably gives worse results.
+///
+/// The default value is \c 1000.
+/// \c -1 means that number of iterations is not limited.
+///
+/// \warning You should specify a reasonable limit for the number of
+/// iterations and/or the number of search steps.
+///
+/// \return <tt>(*this)</tt>
+///
+/// \sa stepLimit(int)
+/// \sa sizeLimit(int)
+GrossoLocatelliPullanMc& iterationLimit(int limit) {
+_iteration_limit = limit;
+return *this;
+}
+/// \brief Sets the maximum number of search steps.
+///
+/// This function sets the maximum number of elementary search steps.
+/// Each iteration of the algorithm finds a maximal clique (but not
+/// necessarily the largest one) by performing several search steps
+/// (node selections).
+///
+/// This limit controls the running time and the success of the
+/// algorithm. For larger values, the algorithm runs slower, but it more
+/// likely finds larger cliques. For smaller values, the algorithm is
+/// faster but probably gives worse results.
+///
+/// The default value is \c -1, which means that number of steps
+/// is not limited explicitly. However, the number of iterations is
+/// limited and each iteration performs a finite number of search steps.
+///
+/// \warning You should specify a reasonable limit for the number of
+/// iterations and/or the number of search steps.
+///
+/// \return <tt>(*this)</tt>
+///
+/// \sa iterationLimit(int)
+/// \sa sizeLimit(int)
+GrossoLocatelliPullanMc& stepLimit(int limit) {
+_step_limit = limit;
+return *this;
+}
+/// \brief Sets the desired clique size.
+///
+/// This function sets the desired clique size that serves as a search
+/// limit. If a clique of this size (or a larger one) is found, then the
+/// algorithm terminates.
+///
+/// This function is especially useful if you know an exact upper bound
+/// for the size of the cliques in the graph or if any clique above
+/// a certain size limit is sufficient for your application.
+///
+/// The default value is \c -1, which means that the size limit is set to
+/// the number of nodes in the graph.
+///
+/// \return <tt>(*this)</tt>
+///
+/// \sa iterationLimit(int)
+/// \sa stepLimit(int)
+GrossoLocatelliPullanMc& sizeLimit(int limit) {
+_size_limit = limit;
+return *this;
+}
+/// \brief The maximum number of iterations.
+///
+/// This function gives back the maximum number of iterations.
+/// \c -1 means that no limit is specified.
+///
+/// \sa iterationLimit(int)
+int iterationLimit() const {
+return _iteration_limit;
+}
+/// \brief The maximum number of search steps.
+///
+/// This function gives back the maximum number of search steps.
+/// \c -1 means that no limit is specified.
+///
+/// \sa stepLimit(int)
+int stepLimit() const {
+return _step_limit;
+}
+/// \brief The desired clique size.
+///
+/// This function gives back the desired clique size that serves as a
+/// search limit. \c -1 means that this limit is set to the number of
+/// nodes in the graph.
+///
+/// \sa sizeLimit(int)
+int sizeLimit() const {
+return _size_limit;
+}
+/// \brief Runs the algorithm.
+///
+/// This function runs the algorithm. If one of the specified limits
+/// is reached, the search process terminates.
+///
 /// \param rule The node selection rule. For more information, see
 /// \ref SelectionRule.
 ///
-/// \return The size of the found clique.
+/// \return The termination cause of the search. For more information,
-int run(int step_num = 100000,
+/// see \ref TerminationCause.
-SelectionRule rule = PENALTY_BASED)
+TerminationCause run(SelectionRule rule = PENALTY_BASED)
 {
 init();
 switch (rule) {
 case RANDOM:
-return start<RandomSelectionRule>(step_num);
+return start<RandomSelectionRule>();
 case DEGREE_BASED:
-return start<DegreeBasedSelectionRule>(step_num);
+return start<DegreeBasedSelectionRule>();
-case PENALTY_BASED:
+default:
-return start<PenaltyBasedSelectionRule>(step_num);
+return start<PenaltyBasedSelectionRule>();
 }
-return 0; // avoid warning
 }
 /// @}
 /// \name Query Functions
+/// The results of the algorithm can be obtained using these functions.\n
+/// The run() function must be called before using them.
 /// @{
 /// \brief The size of the found clique
 ///
 /// This function returns the size of the found clique.
 };
 /// @}
 private:
+// Initialize search options and limits
+void initOptions() {
+// Search options
+_delta_based_restart = true;
+_restart_delta_limit = 4;
+// Search limits
+_iteration_limit = 1000;
+_step_limit = -1;             // this is disabled by default
+_size_limit = -1;             // this is disabled by default
+}
 // Adds a node to the current clique
 void addCliqueNode(int u) {
 if (_clique[u]) return;
 _clique[u] = true;
 _tabu.resize(_n, false);
 }
 // Executes the algorithm
 template <typename SelectionRuleImpl>
-int start(int max_select) {
+TerminationCause start() {
-// Options for the restart rule
+if (_n == 0) return SIZE_LIMIT;
-const bool delta_based_restart = true;
-const int restart_delta_limit = 4;
-if (_n == 0) return 0;
 if (_n == 1) {
 _best_clique[0] = true;
 _best_size = 1;
-return _best_size;
+return SIZE_LIMIT;
 }
-// Iterated local search
+// Iterated local search algorithm
+const int max_size = _size_limit >= 0 ? _size_limit : _n;
+const int max_restart = _iteration_limit >= 0 ?
+_iteration_limit : std::numeric_limits<int>::max();
+const int max_select = _step_limit >= 0 ?
+_step_limit : std::numeric_limits<int>::max();
 SelectionRuleImpl sel_method(*this);
-int select = 0;
+int select = 0, restart = 0;
 IntVector restart_nodes;
+while (select < max_select && restart < max_restart) {
-while (select < max_select) {
 // Perturbation/restart
-if (delta_based_restart) {
+restart++;
+if (_delta_based_restart) {
 restart_nodes.clear();
 for (int i = 0; i != _n; i++) {
-if (_delta[i] >= restart_delta_limit)
+if (_delta[i] >= _restart_delta_limit)
 restart_nodes.push_back(i);
 }
 }
 int rs_node = -1;
 if (restart_nodes.size() > 0) {
 else break;
 }
 if (_size > _best_size) {
 _best_clique = _clique;
 _best_size = _size;
-if (_best_size == _n) return _best_size;
+if (_best_size >= max_size) return SIZE_LIMIT;
 }
 sel_method.update();
 }
-return _best_size;
+return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
 }
 }; //class GrossoLocatelliPullanMc
 ///@}

changeset 934	fe283caf6414
parent 904	c279b19abc62
child 1053	1c978b5bcc65