Changeset 1022:8583fb74238c in lemon
 Timestamp:
 01/08/11 15:52:07 (13 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/grosso_locatelli_pullan_mc.h
r999 r1022 47 47 /// 48 48 /// This class provides a simple but highly efficient and robust heuristic 49 /// method that quickly finds a large clique, but not necessarily the49 /// method that quickly finds a quite large clique, but not necessarily the 50 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 56 /// \tparam GR The undirected graph type the algorithm runs on. … … 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 107 private: 88 108 … … 94 114 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 95 115 116 // The underlying graph 96 117 const GR &_graph; 97 118 IntNodeMap _id; … … 100 121 BoolMatrix _gr; 101 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 133 // The current clique … … 381 411 GrossoLocatelliPullanMc(const GR& graph) : 382 412 _graph(graph), _id(_graph), _rnd(rnd) 383 {} 413 { 414 initOptions(); 415 } 384 416 385 417 /// \brief Constructor with random seed. … … 392 424 GrossoLocatelliPullanMc(const GR& graph, int seed) : 393 425 _graph(graph), _id(_graph), _rnd(seed) 394 {} 426 { 427 initOptions(); 428 } 395 429 396 430 /// \brief Constructor with random number generator. … … 403 437 GrossoLocatelliPullanMc(const GR& graph, const Random& random) : 404 438 _graph(graph), _id(_graph), _rnd(random) 405 {} 439 { 440 initOptions(); 441 } 406 442 407 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 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 418 460 /// likely finds larger cliques. For smaller values, the algorithm is 419 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 564 /// \param rule The node selection rule. For more information, see 421 565 /// \ref SelectionRule. 422 566 /// 423 /// \return The size of the found clique.424 int run(int step_num = 100000,425 567 /// \return The termination cause of the search. For more information, 568 /// see \ref TerminationCause. 569 TerminationCause run(SelectionRule rule = PENALTY_BASED) 426 570 { 427 571 init(); 428 572 switch (rule) { 429 573 case RANDOM: 430 return start<RandomSelectionRule>( step_num);574 return start<RandomSelectionRule>(); 431 575 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 } 437 580 } 438 581 … … 440 583 441 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 … … 531 677 532 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 692 // Adds a node to the current clique … … 587 745 // Executes the algorithm 588 746 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; 595 749 if (_n == 1) { 596 750 _best_clique[0] = true; 597 751 _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 602 762 SelectionRuleImpl sel_method(*this); 603 int select = 0 ;763 int select = 0, restart = 0; 604 764 IntVector restart_nodes; 605 606 while (select < max_select) { 765 while (select < max_select && restart < max_restart) { 607 766 608 767 // Perturbation/restart 609 if (delta_based_restart) { 768 restart++; 769 if (_delta_based_restart) { 610 770 restart_nodes.clear(); 611 771 for (int i = 0; i != _n; i++) { 612 if (_delta[i] >= restart_delta_limit)772 if (_delta[i] >= _restart_delta_limit) 613 773 restart_nodes.push_back(i); 614 774 } … … 664 824 _best_clique = _clique; 665 825 _best_size = _size; 666 if (_best_size == _n) return _best_size;826 if (_best_size >= max_size) return SIZE_LIMIT; 667 827 } 668 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 
test/max_clique_test.cc
r999 r1022 59 59 // Check with general graphs 60 60 template <typename Param> 61 void checkMaxCliqueGeneral( int max_sel,Param rule) {61 void checkMaxCliqueGeneral(Param rule) { 62 62 typedef ListGraph GR; 63 63 typedef GrossoLocatelliPullanMc<GR> McAlg; … … 69 69 GR::NodeMap<bool> map(g); 70 70 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"); 72 73 check(mc.cliqueSize() == 0, "Wrong clique size"); 73 74 check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt"); 74 75 75 76 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"); 77 78 check(mc.cliqueSize() == 1, "Wrong clique size"); 78 79 mc.cliqueMap(map); … … 83 84 84 85 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"); 86 87 check(mc.cliqueSize() == 1, "Wrong clique size"); 87 88 mc.cliqueMap(map); … … 91 92 92 93 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"); 94 95 check(mc.cliqueSize() == 2, "Wrong clique size"); 95 96 mc.cliqueMap(map); … … 111 112 112 113 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"); 114 116 check(mc.cliqueSize() == 4, "Wrong clique size"); 115 117 mc.cliqueMap(map); … … 128 130 // Check with full graphs 129 131 template <typename Param> 130 void checkMaxCliqueFullGraph( int max_sel,Param rule) {132 void checkMaxCliqueFullGraph(Param rule) { 131 133 typedef FullGraph GR; 132 134 typedef GrossoLocatelliPullanMc<FullGraph> McAlg; … … 137 139 GR::NodeMap<bool> map(g); 138 140 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"); 140 142 check(mc.cliqueSize() == size, "Wrong clique size"); 141 143 mc.cliqueMap(map); … … 151 153 // Check with grid graphs 152 154 template <typename Param> 153 void checkMaxCliqueGridGraph( int max_sel,Param rule) {155 void checkMaxCliqueGridGraph(Param rule) { 154 156 GridGraph g(5, 7); 155 157 GridGraph::NodeMap<char> map(g); 156 158 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"); 158 170 check(mc.cliqueSize() == 2, "Wrong clique size"); 159 171 } … … 161 173 162 174 int 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); 166 178 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); 170 182 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); 174 186 175 187 return 0;
Note: See TracChangeset
for help on using the changeset viewer.