COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
11 edited

Legend:

Unmodified
Added
Removed

  • doc/coding_style.dox

    r1023 r463  
    9999\subsection pri-loc-var Private member variables
    100100
    101 Private member variables should start with underscore.
     101Private member variables should start with underscore
    102102
    103103\code
    104 _start_with_underscore
     104_start_with_underscores
    105105\endcode
    106106

  • doc/groups.dox

    r1023 r999  
    407407   strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
    408408
    409 In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
    410 implementations, but the other two algorithms could be faster in special cases.
     409In general NetworkSimplex is the most efficient implementation,
     410but in special cases other algorithms could be faster.
    411411For example, if the total supply and/or capacities are rather small,
    412 \ref CapacityScaling is usually the fastest algorithm (without effective scaling).
     412CapacityScaling is usually the fastest algorithm (without effective scaling).
    413413*/
    414414
    … …  
    472472  \ref dasdan98minmeancycle.
    473473
    474 In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
     474In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
    475475most efficient one, though the best known theoretical bound on its running
    476476time is exponential.
    … …  
    540540
    541541/**
    542 @defgroup planar Planar Embedding and Drawing
     542@defgroup planar Planarity Embedding and Drawing
    543543@ingroup algs
    544544\brief Algorithms for planarity checking, embedding and drawing

  • lemon/capacity_scaling.h

    r1026 r1025  
    9090  /// \warning All input data (capacities, supply values, and costs) must
    9191  /// be integer.
    92   /// \warning This algorithm does not support negative costs for
    93   /// arcs having infinite upper bound.
     92  /// \warning This algorithm does not support negative costs for such
     93  /// arcs that have infinite upper bound.
    9494#ifdef DOXYGEN
    9595  template <typename GR, typename V, typename C, typename TR>
    … …  
    424424    ///
    425425    /// Using this function has the same effect as using \ref supplyMap()
    426     /// with a map in which \c k is assigned to \c s, \c -k is
     426    /// with such a map in which \c k is assigned to \c s, \c -k is
    427427    /// assigned to \c t and all other nodes have zero supply value.
    428428    ///

  • lemon/core.h

    r1023 r988  
    448448  }
    449449
    450   /// \brief Check whether a graph is undirected.
     450  /// Check whether a graph is undirected.
    451451  ///
    452452  /// This function returns \c true if the given graph is undirected.

  • lemon/cost_scaling.h

    r1026 r1025  
    9898  /// "preflow push-relabel" algorithm for the maximum flow problem.
    9999  ///
    100   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
    101   /// implementations available in LEMON for this problem.
    102   ///
    103100  /// Most of the parameters of the problem (except for the digraph)
    104101  /// can be given using separate functions, and the algorithm can be
    … …  
    120117  /// \warning All input data (capacities, supply values, and costs) must
    121118  /// be integer.
    122   /// \warning This algorithm does not support negative costs for
    123   /// arcs having infinite upper bound.
     119  /// \warning This algorithm does not support negative costs for such
     120  /// arcs that have infinite upper bound.
    124121  ///
    125122  /// \note %CostScaling provides three different internal methods,
    … …  
    183180    /// relabel operation.
    184181    /// By default, the so called \ref PARTIAL_AUGMENT
    185     /// "Partial Augment-Relabel" method is used, which turned out to be
     182    /// "Partial Augment-Relabel" method is used, which proved to be
    186183    /// the most efficient and the most robust on various test inputs.
    187184    /// However, the other methods can be selected using the \ref run()
    … …  
    452449    ///
    453450    /// Using this function has the same effect as using \ref supplyMap()
    454     /// with a map in which \c k is assigned to \c s, \c -k is
     451    /// with such a map in which \c k is assigned to \c s, \c -k is
    455452    /// assigned to \c t and all other nodes have zero supply value.
    456453    ///

  • lemon/cycle_canceling.h

    r1026 r1025  
    6969  /// \warning All input data (capacities, supply values, and costs) must
    7070  /// be integer.
    71   /// \warning This algorithm does not support negative costs for
    72   /// arcs having infinite upper bound.
     71  /// \warning This algorithm does not support negative costs for such
     72  /// arcs that have infinite upper bound.
    7373  ///
    7474  /// \note For more information about the three available methods,
    … …  
    118118    /// \ref CycleCanceling provides three different cycle-canceling
    119119    /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
    120     /// is used, which is by far the most efficient and the most robust.
     120    /// is used, which proved to be the most efficient and the most robust
     121    /// on various test inputs.
    121122    /// However, the other methods can be selected using the \ref run()
    122123    /// function with the proper parameter.
    … …  
    350351    ///
    351352    /// Using this function has the same effect as using \ref supplyMap()
    352     /// with a map in which \c k is assigned to \c s, \c -k is
     353    /// with such a map in which \c k is assigned to \c s, \c -k is
    353354    /// assigned to \c t and all other nodes have zero supply value.
    354355    ///

  • lemon/euler.h

    r1023 r956  
    3737  ///Euler tour iterator for digraphs.
    3838
    39   /// \ingroup graph_properties
     39  /// \ingroup graph_prop
    4040  ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
    4141  ///graph (if there exists) and it converts to the \c Arc type of the digraph.

  • lemon/grosso_locatelli_pullan_mc.h

    r1022 r999  
    4747  ///
    4848  /// This class provides a simple but highly efficient and robust heuristic
    49   /// method that quickly finds a quite large clique, but not necessarily the
     49  /// method that quickly finds a 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.
    5551  ///
    5652  /// \tparam GR The undirected graph type the algorithm runs on.
    … …  
    8985    };
    9086
    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 
    10787  private:
    10888
    … …  
    11494    // Note: vector<char> is used instead of vector<bool> for efficiency reasons
    11595
    116     // The underlying graph
    11796    const GR &_graph;
    11897    IntNodeMap _id;
    … …  
    121100    BoolMatrix _gr;
    122101    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;
    132102
    133103    // The current clique
    … …  
    411381    GrossoLocatelliPullanMc(const GR& graph) :
    412382      _graph(graph), _id(_graph), _rnd(rnd)
    413     {
    414       initOptions();
    415     }
     383    {}
    416384
    417385    /// \brief Constructor with random seed.
    … …  
    424392    GrossoLocatelliPullanMc(const GR& graph, int seed) :
    425393      _graph(graph), _id(_graph), _rnd(seed)
    426     {
    427       initOptions();
    428     }
     394    {}
    429395
    430396    /// \brief Constructor with random number generator.
    … …  
    437403    GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
    438404      _graph(graph), _id(_graph), _rnd(random)
    439     {
    440       initOptions();
    441     }
     405    {}
    442406
    443407    /// \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    
    449408    /// @{
    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
     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
    460418    /// likely finds larger cliques. For smaller values, the algorithm is
    461419    /// 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     ///
    564420    /// \param rule The node selection rule. For more information, see
    565421    /// \ref SelectionRule.
    566422    ///
    567     /// \return The termination cause of the search. For more information,
    568     /// see \ref TerminationCause.
    569     TerminationCause run(SelectionRule rule = PENALTY_BASED)
     423    /// \return The size of the found clique.
     424    int run(int step_num = 100000,
     425            SelectionRule rule = PENALTY_BASED)
    570426    {
    571427      init();
    572428      switch (rule) {
    573429        case RANDOM:
    574           return start<RandomSelectionRule>();
     430          return start<RandomSelectionRule>(step_num);
    575431        case DEGREE_BASED:
    576           return start<DegreeBasedSelectionRule>();
    577         default:
    578           return start<PenaltyBasedSelectionRule>();
    579       }
     432          return start<DegreeBasedSelectionRule>(step_num);
     433        case PENALTY_BASED:
     434          return start<PenaltyBasedSelectionRule>(step_num);
     435      }
     436      return 0; // avoid warning
    580437    }
    581438
    … …  
    583440
    584441    /// \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 
    588442    /// @{
    589443
    … …  
    677531
    678532  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     }
    691533
    692534    // Adds a node to the current clique
    … …  
    745587    // Executes the algorithm
    746588    template <typename SelectionRuleImpl>
    747     TerminationCause start() {
    748       if (_n == 0) return SIZE_LIMIT;
     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;
    749595      if (_n == 1) {
    750596        _best_clique[0] = true;
    751597        _best_size = 1;
    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 
     598        return _best_size;
     599      }
     600
     601      // Iterated local search
    762602      SelectionRuleImpl sel_method(*this);
    763       int select = 0, restart = 0;
     603      int select = 0;
    764604      IntVector restart_nodes;
    765       while (select < max_select && restart < max_restart) {
     605
     606      while (select < max_select) {
    766607
    767608        // Perturbation/restart
    768         restart++;
    769         if (_delta_based_restart) {
     609        if (delta_based_restart) {
    770610          restart_nodes.clear();
    771611          for (int i = 0; i != _n; i++) {
    772             if (_delta[i] >= _restart_delta_limit)
     612            if (_delta[i] >= restart_delta_limit)
    773613              restart_nodes.push_back(i);
    774614          }
    … …  
    824664          _best_clique = _clique;
    825665          _best_size = _size;
    826           if (_best_size >= max_size) return SIZE_LIMIT;
     666          if (_best_size == _n) return _best_size;
    827667        }
    828668        sel_method.update();
    829669      }
    830670
    831       return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
     671      return _best_size;
    832672    }
    833673

  • lemon/network_simplex.h

    r1026 r1025  
    4848  /// flow problem.
    4949  ///
    50   /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
    51   /// implementations available in LEMON for this problem.
    52   /// Furthermore, this class supports both directions of the supply/demand
    53   /// inequality constraints. For more information, see \ref SupplyType.
     50  /// In general, %NetworkSimplex is the fastest implementation available
     51  /// in LEMON for this problem.
     52  /// Moreover, it supports both directions of the supply/demand inequality
     53  /// constraints. For more information, see \ref SupplyType.
    5454  ///
    5555  /// Most of the parameters of the problem (except for the digraph)
    … …  
    127127    /// of the algorithm.
    128128    /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
    129     /// turend out to be the most efficient and the most robust on various
     129    /// proved to be the most efficient and the most robust on various
    130130    /// test inputs.
    131131    /// However, another pivot rule can be selected using the \ref run()
    … …  
    169169    typedef std::vector<Cost> CostVector;
    170170    typedef std::vector<signed char> CharVector;
    171     // Note: vector<signed char> is used instead of vector<ArcState> and
     171    // Note: vector<signed char> is used instead of vector<ArcState> and 
    172172    // vector<ArcDirection> for efficiency reasons
    173173
    … …  
    736736    ///
    737737    /// \return <tt>(*this)</tt>
    738     ///
    739     /// \sa supplyType()
    740738    template<typename SupplyMap>
    741739    NetworkSimplex& supplyMap(const SupplyMap& map) {
    … …  
    754752    ///
    755753    /// Using this function has the same effect as using \ref supplyMap()
    756     /// with a map in which \c k is assigned to \c s, \c -k is
     754    /// with such a map in which \c k is assigned to \c s, \c -k is
    757755    /// assigned to \c t and all other nodes have zero supply value.
    758756    ///

  • lemon/path.h

    r1024 r956  
    4444  ///
    4545  /// In a sense, the path can be treated as a list of arcs. The
    46   /// LEMON path type stores just this list. As a consequence, it
     46  /// lemon path type stores just this list. As a consequence, it
    4747  /// cannot enumerate the nodes of the path and the source node of
    4848  /// a zero length path is undefined.
    … …  
    136136    void clear() { head.clear(); tail.clear(); }
    137137
    138     /// \brief The n-th arc.
     138    /// \brief The nth arc.
    139139    ///
    140140    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    … …  
    144144    }
    145145
    146     /// \brief Initialize arc iterator to point to the n-th arc
     146    /// \brief Initialize arc iterator to point to the nth arc
    147147    ///
    148148    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    … …  
    232232  ///
    233233  /// In a sense, the path can be treated as a list of arcs. The
    234   /// LEMON path type stores just this list. As a consequence it
     234  /// lemon path type stores just this list. As a consequence it
    235235  /// cannot enumerate the nodes in the path and the zero length paths
    236236  /// cannot store the source.
    … …  
    328328    void clear() { data.clear(); }
    329329
    330     /// \brief The n-th arc.
     330    /// \brief The nth arc.
    331331    ///
    332332    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    … …  
    335335    }
    336336
    337     /// \brief  Initializes arc iterator to point to the n-th arc.
     337    /// \brief  Initializes arc iterator to point to the nth arc.
    338338    ArcIt nthIt(int n) const {
    339339      return ArcIt(*this, n);
    … …  
    396396  ///
    397397  /// In a sense, the path can be treated as a list of arcs. The
    398   /// LEMON path type stores just this list. As a consequence it
     398  /// lemon path type stores just this list. As a consequence it
    399399  /// cannot enumerate the nodes in the path and the zero length paths
    400400  /// cannot store the source.
    … …  
    505505    };
    506506
    507     /// \brief The n-th arc.
    508     ///
    509     /// This function looks for the n-th arc in O(n) time.
     507    /// \brief The nth arc.
     508    ///
     509    /// This function looks for the nth arc in O(n) time.
    510510    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    511511    const Arc& nth(int n) const {
    … …  
    517517    }
    518518
    519     /// \brief Initializes arc iterator to point to the n-th arc.
     519    /// \brief Initializes arc iterator to point to the nth arc.
    520520    ArcIt nthIt(int n) const {
    521521      Node *node = first;
    … …  
    736736  ///
    737737  /// In a sense, the path can be treated as a list of arcs. The
    738   /// LEMON path type stores just this list. As a consequence it
     738  /// lemon path type stores just this list. As a consequence it
    739739  /// cannot enumerate the nodes in the path and the source node of
    740740  /// a zero length path is undefined.
    … …  
    832832    };
    833833
    834     /// \brief The n-th arc.
     834    /// \brief The nth arc.
    835835    ///
    836836    /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
    … …  
    839839    }
    840840
    841     /// \brief The arc iterator pointing to the n-th arc.
     841    /// \brief The arc iterator pointing to the nth arc.
    842842    ArcIt nthIt(int n) const {
    843843      return ArcIt(*this, n);
    … …  
    10431043  ///
    10441044  /// In a sense, the path can be treated as a list of arcs. The
    1045   /// LEMON path type stores only this list. As a consequence, it
     1045  /// lemon path type stores only this list. As a consequence, it
    10461046  /// cannot enumerate the nodes in the path and the zero length paths
    10471047  /// cannot have a source node.

  • test/max_clique_test.cc

    r1022 r999  
    5959// Check with general graphs
    6060template <typename Param>
    61 void checkMaxCliqueGeneral(Param rule) {
     61void checkMaxCliqueGeneral(int max_sel, Param rule) {
    6262  typedef ListGraph GR;
    6363  typedef GrossoLocatelliPullanMc<GR> McAlg;
    … …  
    6969    GR::NodeMap<bool> map(g);
    7070    McAlg mc(g);
    71     mc.iterationLimit(50);
    72     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
     71    check(mc.run(max_sel, rule) == 0, "Wrong clique size");
    7372    check(mc.cliqueSize() == 0, "Wrong clique size");
    7473    check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
    7574
    7675    GR::Node u = g.addNode();
    77     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
     76    check(mc.run(max_sel, rule) == 1, "Wrong clique size");
    7877    check(mc.cliqueSize() == 1, "Wrong clique size");
    7978    mc.cliqueMap(map);
    … …  
    8483   
    8584    GR::Node v = g.addNode();
    86     check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
     85    check(mc.run(max_sel, rule) == 1, "Wrong clique size");
    8786    check(mc.cliqueSize() == 1, "Wrong clique size");
    8887    mc.cliqueMap(map);
    … …  
    9291
    9392    g.addEdge(u, v);
    94     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
     93    check(mc.run(max_sel, rule) == 2, "Wrong clique size");
    9594    check(mc.cliqueSize() == 2, "Wrong clique size");
    9695    mc.cliqueMap(map);
    … …  
    112111   
    113112    McAlg mc(g);
    114     mc.iterationLimit(50);
    115     check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
     113    check(mc.run(max_sel, rule) == 4, "Wrong clique size");
    116114    check(mc.cliqueSize() == 4, "Wrong clique size");
    117115    mc.cliqueMap(map);
    … …  
    130128// Check with full graphs
    131129template <typename Param>
    132 void checkMaxCliqueFullGraph(Param rule) {
     130void checkMaxCliqueFullGraph(int max_sel, Param rule) {
    133131  typedef FullGraph GR;
    134132  typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
    … …  
    139137    GR::NodeMap<bool> map(g);
    140138    McAlg mc(g);
    141     check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
     139    check(mc.run(max_sel, rule) == size, "Wrong clique size");
    142140    check(mc.cliqueSize() == size, "Wrong clique size");
    143141    mc.cliqueMap(map);
    … …  
    153151// Check with grid graphs
    154152template <typename Param>
    155 void checkMaxCliqueGridGraph(Param rule) {
     153void checkMaxCliqueGridGraph(int max_sel, Param rule) {
    156154  GridGraph g(5, 7);
    157155  GridGraph::NodeMap<char> map(g);
    158156  GrossoLocatelliPullanMc<GridGraph> mc(g);
    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");
     157  check(mc.run(max_sel, rule) == 2, "Wrong clique size");
    170158  check(mc.cliqueSize() == 2, "Wrong clique size");
    171159}
    … …  
    173161
    174162int main() {
    175   checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
    176   checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
    177   checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
     163  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::RANDOM);
     164  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
     165  checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
    178166
    179   checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
    180   checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
    181   checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
     167  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
     168  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
     169  checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
    182170                       
    183   checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
    184   checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
    185   checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
     171  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
     172  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
     173  checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
    186174                       
    187175  return 0;
Note: See TracChangeset for help on using the changeset viewer.