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
2.1 --- a/test/max_clique_test.cc Tue Nov 16 07:46:01 2010 +0100
2.2 +++ b/test/max_clique_test.cc Sat Jan 08 15:52:07 2011 +0100
2.3 @@ -58,7 +58,7 @@
2.4
2.5 // Check with general graphs
2.6 template <typename Param>
2.7 -void checkMaxCliqueGeneral(int max_sel, Param rule) {
2.8 +void checkMaxCliqueGeneral(Param rule) {
2.9 typedef ListGraph GR;
2.10 typedef GrossoLocatelliPullanMc<GR> McAlg;
2.11 typedef McAlg::CliqueNodeIt CliqueIt;
2.12 @@ -68,12 +68,13 @@
2.13 GR g;
2.14 GR::NodeMap<bool> map(g);
2.15 McAlg mc(g);
2.16 - check(mc.run(max_sel, rule) == 0, "Wrong clique size");
2.17 + mc.iterationLimit(50);
2.18 + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
2.19 check(mc.cliqueSize() == 0, "Wrong clique size");
2.20 check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
2.21
2.22 GR::Node u = g.addNode();
2.23 - check(mc.run(max_sel, rule) == 1, "Wrong clique size");
2.24 + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
2.25 check(mc.cliqueSize() == 1, "Wrong clique size");
2.26 mc.cliqueMap(map);
2.27 check(map[u], "Wrong clique map");
2.28 @@ -82,7 +83,7 @@
2.29 "Wrong CliqueNodeIt");
2.30
2.31 GR::Node v = g.addNode();
2.32 - check(mc.run(max_sel, rule) == 1, "Wrong clique size");
2.33 + check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
2.34 check(mc.cliqueSize() == 1, "Wrong clique size");
2.35 mc.cliqueMap(map);
2.36 check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
2.37 @@ -90,7 +91,7 @@
2.38 check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
2.39
2.40 g.addEdge(u, v);
2.41 - check(mc.run(max_sel, rule) == 2, "Wrong clique size");
2.42 + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
2.43 check(mc.cliqueSize() == 2, "Wrong clique size");
2.44 mc.cliqueMap(map);
2.45 check(map[u] && map[v], "Wrong clique map");
2.46 @@ -110,7 +111,8 @@
2.47 .run();
2.48
2.49 McAlg mc(g);
2.50 - check(mc.run(max_sel, rule) == 4, "Wrong clique size");
2.51 + mc.iterationLimit(50);
2.52 + check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
2.53 check(mc.cliqueSize() == 4, "Wrong clique size");
2.54 mc.cliqueMap(map);
2.55 for (GR::NodeIt n(g); n != INVALID; ++n) {
2.56 @@ -127,7 +129,7 @@
2.57
2.58 // Check with full graphs
2.59 template <typename Param>
2.60 -void checkMaxCliqueFullGraph(int max_sel, Param rule) {
2.61 +void checkMaxCliqueFullGraph(Param rule) {
2.62 typedef FullGraph GR;
2.63 typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
2.64 typedef McAlg::CliqueNodeIt CliqueIt;
2.65 @@ -136,7 +138,7 @@
2.66 GR g(size);
2.67 GR::NodeMap<bool> map(g);
2.68 McAlg mc(g);
2.69 - check(mc.run(max_sel, rule) == size, "Wrong clique size");
2.70 + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
2.71 check(mc.cliqueSize() == size, "Wrong clique size");
2.72 mc.cliqueMap(map);
2.73 for (GR::NodeIt n(g); n != INVALID; ++n) {
2.74 @@ -150,27 +152,37 @@
2.75
2.76 // Check with grid graphs
2.77 template <typename Param>
2.78 -void checkMaxCliqueGridGraph(int max_sel, Param rule) {
2.79 +void checkMaxCliqueGridGraph(Param rule) {
2.80 GridGraph g(5, 7);
2.81 GridGraph::NodeMap<char> map(g);
2.82 GrossoLocatelliPullanMc<GridGraph> mc(g);
2.83 - check(mc.run(max_sel, rule) == 2, "Wrong clique size");
2.84 +
2.85 + mc.iterationLimit(100);
2.86 + check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause");
2.87 + check(mc.cliqueSize() == 2, "Wrong clique size");
2.88 +
2.89 + mc.stepLimit(100);
2.90 + check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause");
2.91 + check(mc.cliqueSize() == 2, "Wrong clique size");
2.92 +
2.93 + mc.sizeLimit(2);
2.94 + check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause");
2.95 check(mc.cliqueSize() == 2, "Wrong clique size");
2.96 }
2.97
2.98
2.99 int main() {
2.100 - checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::RANDOM);
2.101 - checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
2.102 - checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
2.103 + checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
2.104 + checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
2.105 + checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
2.106
2.107 - checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
2.108 - checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
2.109 - checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
2.110 + checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
2.111 + checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
2.112 + checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
2.113
2.114 - checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
2.115 - checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
2.116 - checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
2.117 + checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
2.118 + checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
2.119 + checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
2.120
2.121 return 0;
2.122 }