1.1 --- a/doc/coding_style.dox Sat Jan 08 16:11:48 2011 +0100
1.2 +++ b/doc/coding_style.dox Mon Jan 10 09:34:50 2011 +0100
1.3 @@ -98,10 +98,10 @@
1.4
1.5 \subsection pri-loc-var Private member variables
1.6
1.7 -Private member variables should start with underscore
1.8 +Private member variables should start with underscore.
1.9
1.10 \code
1.11 -_start_with_underscores
1.12 +_start_with_underscore
1.13 \endcode
1.14
1.15 \subsection cs-excep Exceptions
2.1 --- a/doc/groups.dox Sat Jan 08 16:11:48 2011 +0100
2.2 +++ b/doc/groups.dox Mon Jan 10 09:34:50 2011 +0100
2.3 @@ -406,10 +406,10 @@
2.4 - \ref CycleCanceling Cycle-Canceling algorithms, two of which are
2.5 strongly polynomial \ref klein67primal, \ref goldberg89cyclecanceling.
2.6
2.7 -In general NetworkSimplex is the most efficient implementation,
2.8 -but in special cases other algorithms could be faster.
2.9 +In general, \ref NetworkSimplex and \ref CostScaling are the most efficient
2.10 +implementations, but the other two algorithms could be faster in special cases.
2.11 For example, if the total supply and/or capacities are rather small,
2.12 -CapacityScaling is usually the fastest algorithm (without effective scaling).
2.13 +\ref CapacityScaling is usually the fastest algorithm (without effective scaling).
2.14 */
2.15
2.16 /**
2.17 @@ -471,7 +471,7 @@
2.18 - \ref HowardMmc Howard's policy iteration algorithm
2.19 \ref dasdan98minmeancycle.
2.20
2.21 -In practice, the \ref HowardMmc "Howard" algorithm proved to be by far the
2.22 +In practice, the \ref HowardMmc "Howard" algorithm turned out to be by far the
2.23 most efficient one, though the best known theoretical bound on its running
2.24 time is exponential.
2.25 Both \ref KarpMmc "Karp" and \ref HartmannOrlinMmc "Hartmann-Orlin" algorithms
2.26 @@ -539,7 +539,7 @@
2.27 */
2.28
2.29 /**
2.30 -@defgroup planar Planarity Embedding and Drawing
2.31 +@defgroup planar Planar Embedding and Drawing
2.32 @ingroup algs
2.33 \brief Algorithms for planarity checking, embedding and drawing
2.34
3.1 --- a/lemon/capacity_scaling.h Sat Jan 08 16:11:48 2011 +0100
3.2 +++ b/lemon/capacity_scaling.h Mon Jan 10 09:34:50 2011 +0100
3.3 @@ -89,8 +89,8 @@
3.4 /// \warning Both \c V and \c C must be signed number types.
3.5 /// \warning All input data (capacities, supply values, and costs) must
3.6 /// be integer.
3.7 - /// \warning This algorithm does not support negative costs for such
3.8 - /// arcs that have infinite upper bound.
3.9 + /// \warning This algorithm does not support negative costs for
3.10 + /// arcs having infinite upper bound.
3.11 #ifdef DOXYGEN
3.12 template <typename GR, typename V, typename C, typename TR>
3.13 #else
3.14 @@ -423,7 +423,7 @@
3.15 /// calling \ref run(), the supply of each node will be set to zero.
3.16 ///
3.17 /// Using this function has the same effect as using \ref supplyMap()
3.18 - /// with such a map in which \c k is assigned to \c s, \c -k is
3.19 + /// with a map in which \c k is assigned to \c s, \c -k is
3.20 /// assigned to \c t and all other nodes have zero supply value.
3.21 ///
3.22 /// \param s The source node.
4.1 --- a/lemon/core.h Sat Jan 08 16:11:48 2011 +0100
4.2 +++ b/lemon/core.h Mon Jan 10 09:34:50 2011 +0100
4.3 @@ -447,7 +447,7 @@
4.4
4.5 }
4.6
4.7 - /// Check whether a graph is undirected.
4.8 + /// \brief Check whether a graph is undirected.
4.9 ///
4.10 /// This function returns \c true if the given graph is undirected.
4.11 #ifdef DOXYGEN
5.1 --- a/lemon/cost_scaling.h Sat Jan 08 16:11:48 2011 +0100
5.2 +++ b/lemon/cost_scaling.h Mon Jan 10 09:34:50 2011 +0100
5.3 @@ -97,6 +97,9 @@
5.4 /// can be viewed as the generalization of the \ref Preflow
5.5 /// "preflow push-relabel" algorithm for the maximum flow problem.
5.6 ///
5.7 + /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
5.8 + /// implementations available in LEMON for this problem.
5.9 + ///
5.10 /// Most of the parameters of the problem (except for the digraph)
5.11 /// can be given using separate functions, and the algorithm can be
5.12 /// executed using the \ref run() function. If some parameters are not
5.13 @@ -116,8 +119,8 @@
5.14 /// \warning Both \c V and \c C must be signed number types.
5.15 /// \warning All input data (capacities, supply values, and costs) must
5.16 /// be integer.
5.17 - /// \warning This algorithm does not support negative costs for such
5.18 - /// arcs that have infinite upper bound.
5.19 + /// \warning This algorithm does not support negative costs for
5.20 + /// arcs having infinite upper bound.
5.21 ///
5.22 /// \note %CostScaling provides three different internal methods,
5.23 /// from which the most efficient one is used by default.
5.24 @@ -179,7 +182,7 @@
5.25 /// in their base operations, which are used in conjunction with the
5.26 /// relabel operation.
5.27 /// By default, the so called \ref PARTIAL_AUGMENT
5.28 - /// "Partial Augment-Relabel" method is used, which proved to be
5.29 + /// "Partial Augment-Relabel" method is used, which turned out to be
5.30 /// the most efficient and the most robust on various test inputs.
5.31 /// However, the other methods can be selected using the \ref run()
5.32 /// function with the proper parameter.
5.33 @@ -448,7 +451,7 @@
5.34 /// calling \ref run(), the supply of each node will be set to zero.
5.35 ///
5.36 /// Using this function has the same effect as using \ref supplyMap()
5.37 - /// with such a map in which \c k is assigned to \c s, \c -k is
5.38 + /// with a map in which \c k is assigned to \c s, \c -k is
5.39 /// assigned to \c t and all other nodes have zero supply value.
5.40 ///
5.41 /// \param s The source node.
6.1 --- a/lemon/cycle_canceling.h Sat Jan 08 16:11:48 2011 +0100
6.2 +++ b/lemon/cycle_canceling.h Mon Jan 10 09:34:50 2011 +0100
6.3 @@ -68,8 +68,8 @@
6.4 /// \warning Both \c V and \c C must be signed number types.
6.5 /// \warning All input data (capacities, supply values, and costs) must
6.6 /// be integer.
6.7 - /// \warning This algorithm does not support negative costs for such
6.8 - /// arcs that have infinite upper bound.
6.9 + /// \warning This algorithm does not support negative costs for
6.10 + /// arcs having infinite upper bound.
6.11 ///
6.12 /// \note For more information about the three available methods,
6.13 /// see \ref Method.
6.14 @@ -117,8 +117,7 @@
6.15 ///
6.16 /// \ref CycleCanceling provides three different cycle-canceling
6.17 /// methods. By default, \ref CANCEL_AND_TIGHTEN "Cancel and Tighten"
6.18 - /// is used, which proved to be the most efficient and the most robust
6.19 - /// on various test inputs.
6.20 + /// is used, which is by far the most efficient and the most robust.
6.21 /// However, the other methods can be selected using the \ref run()
6.22 /// function with the proper parameter.
6.23 enum Method {
6.24 @@ -350,7 +349,7 @@
6.25 /// calling \ref run(), the supply of each node will be set to zero.
6.26 ///
6.27 /// Using this function has the same effect as using \ref supplyMap()
6.28 - /// with such a map in which \c k is assigned to \c s, \c -k is
6.29 + /// with a map in which \c k is assigned to \c s, \c -k is
6.30 /// assigned to \c t and all other nodes have zero supply value.
6.31 ///
6.32 /// \param s The source node.
7.1 --- a/lemon/euler.h Sat Jan 08 16:11:48 2011 +0100
7.2 +++ b/lemon/euler.h Mon Jan 10 09:34:50 2011 +0100
7.3 @@ -36,7 +36,7 @@
7.4
7.5 ///Euler tour iterator for digraphs.
7.6
7.7 - /// \ingroup graph_prop
7.8 + /// \ingroup graph_properties
7.9 ///This iterator provides an Euler tour (Eulerian circuit) of a \e directed
7.10 ///graph (if there exists) and it converts to the \c Arc type of the digraph.
7.11 ///
8.1 --- a/lemon/grosso_locatelli_pullan_mc.h Sat Jan 08 16:11:48 2011 +0100
8.2 +++ b/lemon/grosso_locatelli_pullan_mc.h Mon Jan 10 09:34:50 2011 +0100
8.3 @@ -46,8 +46,12 @@
8.4 /// pair of nodes is connected.
8.5 ///
8.6 /// This class provides a simple but highly efficient and robust heuristic
8.7 - /// method that quickly finds a large clique, but not necessarily the
8.8 + /// method that quickly finds a quite large clique, but not necessarily the
8.9 /// largest one.
8.10 + /// The algorithm performs a certain number of iterations to find several
8.11 + /// cliques and selects the largest one among them. Various limits can be
8.12 + /// specified to control the running time and the effectiveness of the
8.13 + /// search process.
8.14 ///
8.15 /// \tparam GR The undirected graph type the algorithm runs on.
8.16 ///
8.17 @@ -84,6 +88,22 @@
8.18 PENALTY_BASED
8.19 };
8.20
8.21 + /// \brief Constants for the causes of search termination.
8.22 + ///
8.23 + /// Enum type containing constants for the different causes of search
8.24 + /// termination. The \ref run() function returns one of these values.
8.25 + enum TerminationCause {
8.26 +
8.27 + /// The iteration count limit is reached.
8.28 + ITERATION_LIMIT,
8.29 +
8.30 + /// The step count limit is reached.
8.31 + STEP_LIMIT,
8.32 +
8.33 + /// The clique size limit is reached.
8.34 + SIZE_LIMIT
8.35 + };
8.36 +
8.37 private:
8.38
8.39 TEMPLATE_GRAPH_TYPEDEFS(GR);
8.40 @@ -93,12 +113,22 @@
8.41 typedef std::vector<BoolVector> BoolMatrix;
8.42 // Note: vector<char> is used instead of vector<bool> for efficiency reasons
8.43
8.44 + // The underlying graph
8.45 const GR &_graph;
8.46 IntNodeMap _id;
8.47
8.48 // Internal matrix representation of the graph
8.49 BoolMatrix _gr;
8.50 int _n;
8.51 +
8.52 + // Search options
8.53 + bool _delta_based_restart;
8.54 + int _restart_delta_limit;
8.55 +
8.56 + // Search limits
8.57 + int _iteration_limit;
8.58 + int _step_limit;
8.59 + int _size_limit;
8.60
8.61 // The current clique
8.62 BoolVector _clique;
8.63 @@ -380,7 +410,9 @@
8.64 /// \param graph The undirected graph the algorithm runs on.
8.65 GrossoLocatelliPullanMc(const GR& graph) :
8.66 _graph(graph), _id(_graph), _rnd(rnd)
8.67 - {}
8.68 + {
8.69 + initOptions();
8.70 + }
8.71
8.72 /// \brief Constructor with random seed.
8.73 ///
8.74 @@ -391,7 +423,9 @@
8.75 /// that is used during the algorithm.
8.76 GrossoLocatelliPullanMc(const GR& graph, int seed) :
8.77 _graph(graph), _id(_graph), _rnd(seed)
8.78 - {}
8.79 + {
8.80 + initOptions();
8.81 + }
8.82
8.83 /// \brief Constructor with random number generator.
8.84 ///
8.85 @@ -402,43 +436,155 @@
8.86 /// algorithm.
8.87 GrossoLocatelliPullanMc(const GR& graph, const Random& random) :
8.88 _graph(graph), _id(_graph), _rnd(random)
8.89 - {}
8.90 + {
8.91 + initOptions();
8.92 + }
8.93
8.94 /// \name Execution Control
8.95 + /// The \ref run() function can be used to execute the algorithm.\n
8.96 + /// The functions \ref iterationLimit(int), \ref stepLimit(int), and
8.97 + /// \ref sizeLimit(int) can be used to specify various limits for the
8.98 + /// search process.
8.99 +
8.100 /// @{
8.101 +
8.102 + /// \brief Sets the maximum number of iterations.
8.103 + ///
8.104 + /// This function sets the maximum number of iterations.
8.105 + /// Each iteration of the algorithm finds a maximal clique (but not
8.106 + /// necessarily the largest one) by performing several search steps
8.107 + /// (node selections).
8.108 + ///
8.109 + /// This limit controls the running time and the success of the
8.110 + /// algorithm. For larger values, the algorithm runs slower, but it more
8.111 + /// likely finds larger cliques. For smaller values, the algorithm is
8.112 + /// faster but probably gives worse results.
8.113 + ///
8.114 + /// The default value is \c 1000.
8.115 + /// \c -1 means that number of iterations is not limited.
8.116 + ///
8.117 + /// \warning You should specify a reasonable limit for the number of
8.118 + /// iterations and/or the number of search steps.
8.119 + ///
8.120 + /// \return <tt>(*this)</tt>
8.121 + ///
8.122 + /// \sa stepLimit(int)
8.123 + /// \sa sizeLimit(int)
8.124 + GrossoLocatelliPullanMc& iterationLimit(int limit) {
8.125 + _iteration_limit = limit;
8.126 + return *this;
8.127 + }
8.128 +
8.129 + /// \brief Sets the maximum number of search steps.
8.130 + ///
8.131 + /// This function sets the maximum number of elementary search steps.
8.132 + /// Each iteration of the algorithm finds a maximal clique (but not
8.133 + /// necessarily the largest one) by performing several search steps
8.134 + /// (node selections).
8.135 + ///
8.136 + /// This limit controls the running time and the success of the
8.137 + /// algorithm. For larger values, the algorithm runs slower, but it more
8.138 + /// likely finds larger cliques. For smaller values, the algorithm is
8.139 + /// faster but probably gives worse results.
8.140 + ///
8.141 + /// The default value is \c -1, which means that number of steps
8.142 + /// is not limited explicitly. However, the number of iterations is
8.143 + /// limited and each iteration performs a finite number of search steps.
8.144 + ///
8.145 + /// \warning You should specify a reasonable limit for the number of
8.146 + /// iterations and/or the number of search steps.
8.147 + ///
8.148 + /// \return <tt>(*this)</tt>
8.149 + ///
8.150 + /// \sa iterationLimit(int)
8.151 + /// \sa sizeLimit(int)
8.152 + GrossoLocatelliPullanMc& stepLimit(int limit) {
8.153 + _step_limit = limit;
8.154 + return *this;
8.155 + }
8.156 +
8.157 + /// \brief Sets the desired clique size.
8.158 + ///
8.159 + /// This function sets the desired clique size that serves as a search
8.160 + /// limit. If a clique of this size (or a larger one) is found, then the
8.161 + /// algorithm terminates.
8.162 + ///
8.163 + /// This function is especially useful if you know an exact upper bound
8.164 + /// for the size of the cliques in the graph or if any clique above
8.165 + /// a certain size limit is sufficient for your application.
8.166 + ///
8.167 + /// The default value is \c -1, which means that the size limit is set to
8.168 + /// the number of nodes in the graph.
8.169 + ///
8.170 + /// \return <tt>(*this)</tt>
8.171 + ///
8.172 + /// \sa iterationLimit(int)
8.173 + /// \sa stepLimit(int)
8.174 + GrossoLocatelliPullanMc& sizeLimit(int limit) {
8.175 + _size_limit = limit;
8.176 + return *this;
8.177 + }
8.178 +
8.179 + /// \brief The maximum number of iterations.
8.180 + ///
8.181 + /// This function gives back the maximum number of iterations.
8.182 + /// \c -1 means that no limit is specified.
8.183 + ///
8.184 + /// \sa iterationLimit(int)
8.185 + int iterationLimit() const {
8.186 + return _iteration_limit;
8.187 + }
8.188 +
8.189 + /// \brief The maximum number of search steps.
8.190 + ///
8.191 + /// This function gives back the maximum number of search steps.
8.192 + /// \c -1 means that no limit is specified.
8.193 + ///
8.194 + /// \sa stepLimit(int)
8.195 + int stepLimit() const {
8.196 + return _step_limit;
8.197 + }
8.198 +
8.199 + /// \brief The desired clique size.
8.200 + ///
8.201 + /// This function gives back the desired clique size that serves as a
8.202 + /// search limit. \c -1 means that this limit is set to the number of
8.203 + /// nodes in the graph.
8.204 + ///
8.205 + /// \sa sizeLimit(int)
8.206 + int sizeLimit() const {
8.207 + return _size_limit;
8.208 + }
8.209
8.210 /// \brief Runs the algorithm.
8.211 ///
8.212 - /// This function runs the algorithm.
8.213 + /// This function runs the algorithm. If one of the specified limits
8.214 + /// is reached, the search process terminates.
8.215 ///
8.216 - /// \param step_num The maximum number of node selections (steps)
8.217 - /// during the search process.
8.218 - /// This parameter controls the running time and the success of the
8.219 - /// algorithm. For larger values, the algorithm runs slower but it more
8.220 - /// likely finds larger cliques. For smaller values, the algorithm is
8.221 - /// faster but probably gives worse results.
8.222 /// \param rule The node selection rule. For more information, see
8.223 /// \ref SelectionRule.
8.224 ///
8.225 - /// \return The size of the found clique.
8.226 - int run(int step_num = 100000,
8.227 - SelectionRule rule = PENALTY_BASED)
8.228 + /// \return The termination cause of the search. For more information,
8.229 + /// see \ref TerminationCause.
8.230 + TerminationCause run(SelectionRule rule = PENALTY_BASED)
8.231 {
8.232 init();
8.233 switch (rule) {
8.234 case RANDOM:
8.235 - return start<RandomSelectionRule>(step_num);
8.236 + return start<RandomSelectionRule>();
8.237 case DEGREE_BASED:
8.238 - return start<DegreeBasedSelectionRule>(step_num);
8.239 - case PENALTY_BASED:
8.240 - return start<PenaltyBasedSelectionRule>(step_num);
8.241 + return start<DegreeBasedSelectionRule>();
8.242 + default:
8.243 + return start<PenaltyBasedSelectionRule>();
8.244 }
8.245 - return 0; // avoid warning
8.246 }
8.247
8.248 /// @}
8.249
8.250 /// \name Query Functions
8.251 + /// The results of the algorithm can be obtained using these functions.\n
8.252 + /// The run() function must be called before using them.
8.253 +
8.254 /// @{
8.255
8.256 /// \brief The size of the found clique
8.257 @@ -530,6 +676,18 @@
8.258 /// @}
8.259
8.260 private:
8.261 +
8.262 + // Initialize search options and limits
8.263 + void initOptions() {
8.264 + // Search options
8.265 + _delta_based_restart = true;
8.266 + _restart_delta_limit = 4;
8.267 +
8.268 + // Search limits
8.269 + _iteration_limit = 1000;
8.270 + _step_limit = -1; // this is disabled by default
8.271 + _size_limit = -1; // this is disabled by default
8.272 + }
8.273
8.274 // Adds a node to the current clique
8.275 void addCliqueNode(int u) {
8.276 @@ -586,30 +744,32 @@
8.277
8.278 // Executes the algorithm
8.279 template <typename SelectionRuleImpl>
8.280 - int start(int max_select) {
8.281 - // Options for the restart rule
8.282 - const bool delta_based_restart = true;
8.283 - const int restart_delta_limit = 4;
8.284 -
8.285 - if (_n == 0) return 0;
8.286 + TerminationCause start() {
8.287 + if (_n == 0) return SIZE_LIMIT;
8.288 if (_n == 1) {
8.289 _best_clique[0] = true;
8.290 _best_size = 1;
8.291 - return _best_size;
8.292 + return SIZE_LIMIT;
8.293 }
8.294
8.295 - // Iterated local search
8.296 + // Iterated local search algorithm
8.297 + const int max_size = _size_limit >= 0 ? _size_limit : _n;
8.298 + const int max_restart = _iteration_limit >= 0 ?
8.299 + _iteration_limit : std::numeric_limits<int>::max();
8.300 + const int max_select = _step_limit >= 0 ?
8.301 + _step_limit : std::numeric_limits<int>::max();
8.302 +
8.303 SelectionRuleImpl sel_method(*this);
8.304 - int select = 0;
8.305 + int select = 0, restart = 0;
8.306 IntVector restart_nodes;
8.307 -
8.308 - while (select < max_select) {
8.309 + while (select < max_select && restart < max_restart) {
8.310
8.311 // Perturbation/restart
8.312 - if (delta_based_restart) {
8.313 + restart++;
8.314 + if (_delta_based_restart) {
8.315 restart_nodes.clear();
8.316 for (int i = 0; i != _n; i++) {
8.317 - if (_delta[i] >= restart_delta_limit)
8.318 + if (_delta[i] >= _restart_delta_limit)
8.319 restart_nodes.push_back(i);
8.320 }
8.321 }
8.322 @@ -663,12 +823,12 @@
8.323 if (_size > _best_size) {
8.324 _best_clique = _clique;
8.325 _best_size = _size;
8.326 - if (_best_size == _n) return _best_size;
8.327 + if (_best_size >= max_size) return SIZE_LIMIT;
8.328 }
8.329 sel_method.update();
8.330 }
8.331
8.332 - return _best_size;
8.333 + return (restart >= max_restart ? ITERATION_LIMIT : STEP_LIMIT);
8.334 }
8.335
8.336 }; //class GrossoLocatelliPullanMc
9.1 --- a/lemon/network_simplex.h Sat Jan 08 16:11:48 2011 +0100
9.2 +++ b/lemon/network_simplex.h Mon Jan 10 09:34:50 2011 +0100
9.3 @@ -47,10 +47,10 @@
9.4 /// linear programming simplex method directly for the minimum cost
9.5 /// flow problem.
9.6 ///
9.7 - /// In general, %NetworkSimplex is the fastest implementation available
9.8 - /// in LEMON for this problem.
9.9 - /// Moreover, it supports both directions of the supply/demand inequality
9.10 - /// constraints. For more information, see \ref SupplyType.
9.11 + /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
9.12 + /// implementations available in LEMON for this problem.
9.13 + /// Furthermore, this class supports both directions of the supply/demand
9.14 + /// inequality constraints. For more information, see \ref SupplyType.
9.15 ///
9.16 /// Most of the parameters of the problem (except for the digraph)
9.17 /// can be given using separate functions, and the algorithm can be
9.18 @@ -126,7 +126,7 @@
9.19 /// implementations that significantly affect the running time
9.20 /// of the algorithm.
9.21 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which
9.22 - /// proved to be the most efficient and the most robust on various
9.23 + /// turend out to be the most efficient and the most robust on various
9.24 /// test inputs.
9.25 /// However, another pivot rule can be selected using the \ref run()
9.26 /// function with the proper parameter.
9.27 @@ -168,7 +168,7 @@
9.28 typedef std::vector<Value> ValueVector;
9.29 typedef std::vector<Cost> CostVector;
9.30 typedef std::vector<signed char> CharVector;
9.31 - // Note: vector<signed char> is used instead of vector<ArcState> and
9.32 + // Note: vector<signed char> is used instead of vector<ArcState> and
9.33 // vector<ArcDirection> for efficiency reasons
9.34
9.35 // State constants for arcs
9.36 @@ -735,6 +735,8 @@
9.37 /// of the algorithm.
9.38 ///
9.39 /// \return <tt>(*this)</tt>
9.40 + ///
9.41 + /// \sa supplyType()
9.42 template<typename SupplyMap>
9.43 NetworkSimplex& supplyMap(const SupplyMap& map) {
9.44 for (NodeIt n(_graph); n != INVALID; ++n) {
9.45 @@ -751,7 +753,7 @@
9.46 /// calling \ref run(), the supply of each node will be set to zero.
9.47 ///
9.48 /// Using this function has the same effect as using \ref supplyMap()
9.49 - /// with such a map in which \c k is assigned to \c s, \c -k is
9.50 + /// with a map in which \c k is assigned to \c s, \c -k is
9.51 /// assigned to \c t and all other nodes have zero supply value.
9.52 ///
9.53 /// \param s The source node.
10.1 --- a/lemon/path.h Sat Jan 08 16:11:48 2011 +0100
10.2 +++ b/lemon/path.h Mon Jan 10 09:34:50 2011 +0100
10.3 @@ -43,7 +43,7 @@
10.4 /// \tparam GR The digraph type in which the path is.
10.5 ///
10.6 /// In a sense, the path can be treated as a list of arcs. The
10.7 - /// lemon path type stores just this list. As a consequence, it
10.8 + /// LEMON path type stores just this list. As a consequence, it
10.9 /// cannot enumerate the nodes of the path and the source node of
10.10 /// a zero length path is undefined.
10.11 ///
10.12 @@ -135,7 +135,7 @@
10.13 /// \brief Reset the path to an empty one.
10.14 void clear() { head.clear(); tail.clear(); }
10.15
10.16 - /// \brief The nth arc.
10.17 + /// \brief The n-th arc.
10.18 ///
10.19 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
10.20 const Arc& nth(int n) const {
10.21 @@ -143,7 +143,7 @@
10.22 *(tail.begin() + (n - head.size()));
10.23 }
10.24
10.25 - /// \brief Initialize arc iterator to point to the nth arc
10.26 + /// \brief Initialize arc iterator to point to the n-th arc
10.27 ///
10.28 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
10.29 ArcIt nthIt(int n) const {
10.30 @@ -231,7 +231,7 @@
10.31 /// \tparam GR The digraph type in which the path is.
10.32 ///
10.33 /// In a sense, the path can be treated as a list of arcs. The
10.34 - /// lemon path type stores just this list. As a consequence it
10.35 + /// LEMON path type stores just this list. As a consequence it
10.36 /// cannot enumerate the nodes in the path and the zero length paths
10.37 /// cannot store the source.
10.38 ///
10.39 @@ -327,14 +327,14 @@
10.40 /// \brief Reset the path to an empty one.
10.41 void clear() { data.clear(); }
10.42
10.43 - /// \brief The nth arc.
10.44 + /// \brief The n-th arc.
10.45 ///
10.46 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
10.47 const Arc& nth(int n) const {
10.48 return data[n];
10.49 }
10.50
10.51 - /// \brief Initializes arc iterator to point to the nth arc.
10.52 + /// \brief Initializes arc iterator to point to the n-th arc.
10.53 ArcIt nthIt(int n) const {
10.54 return ArcIt(*this, n);
10.55 }
10.56 @@ -395,7 +395,7 @@
10.57 /// \tparam GR The digraph type in which the path is.
10.58 ///
10.59 /// In a sense, the path can be treated as a list of arcs. The
10.60 - /// lemon path type stores just this list. As a consequence it
10.61 + /// LEMON path type stores just this list. As a consequence it
10.62 /// cannot enumerate the nodes in the path and the zero length paths
10.63 /// cannot store the source.
10.64 ///
10.65 @@ -504,9 +504,9 @@
10.66 Node *node;
10.67 };
10.68
10.69 - /// \brief The nth arc.
10.70 + /// \brief The n-th arc.
10.71 ///
10.72 - /// This function looks for the nth arc in O(n) time.
10.73 + /// This function looks for the n-th arc in O(n) time.
10.74 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
10.75 const Arc& nth(int n) const {
10.76 Node *node = first;
10.77 @@ -516,7 +516,7 @@
10.78 return node->arc;
10.79 }
10.80
10.81 - /// \brief Initializes arc iterator to point to the nth arc.
10.82 + /// \brief Initializes arc iterator to point to the n-th arc.
10.83 ArcIt nthIt(int n) const {
10.84 Node *node = first;
10.85 for (int i = 0; i < n; ++i) {
10.86 @@ -735,7 +735,7 @@
10.87 /// \tparam GR The digraph type in which the path is.
10.88 ///
10.89 /// In a sense, the path can be treated as a list of arcs. The
10.90 - /// lemon path type stores just this list. As a consequence it
10.91 + /// LEMON path type stores just this list. As a consequence it
10.92 /// cannot enumerate the nodes in the path and the source node of
10.93 /// a zero length path is undefined.
10.94 ///
10.95 @@ -831,14 +831,14 @@
10.96 int idx;
10.97 };
10.98
10.99 - /// \brief The nth arc.
10.100 + /// \brief The n-th arc.
10.101 ///
10.102 /// \pre \c n is in the <tt>[0..length() - 1]</tt> range.
10.103 const Arc& nth(int n) const {
10.104 return arcs[n];
10.105 }
10.106
10.107 - /// \brief The arc iterator pointing to the nth arc.
10.108 + /// \brief The arc iterator pointing to the n-th arc.
10.109 ArcIt nthIt(int n) const {
10.110 return ArcIt(*this, n);
10.111 }
10.112 @@ -1042,7 +1042,7 @@
10.113 /// \brief Class which helps to iterate through the nodes of a path
10.114 ///
10.115 /// In a sense, the path can be treated as a list of arcs. The
10.116 - /// lemon path type stores only this list. As a consequence, it
10.117 + /// LEMON path type stores only this list. As a consequence, it
10.118 /// cannot enumerate the nodes in the path and the zero length paths
10.119 /// cannot have a source node.
10.120 ///
11.1 --- a/test/max_clique_test.cc Sat Jan 08 16:11:48 2011 +0100
11.2 +++ b/test/max_clique_test.cc Mon Jan 10 09:34:50 2011 +0100
11.3 @@ -58,7 +58,7 @@
11.4
11.5 // Check with general graphs
11.6 template <typename Param>
11.7 -void checkMaxCliqueGeneral(int max_sel, Param rule) {
11.8 +void checkMaxCliqueGeneral(Param rule) {
11.9 typedef ListGraph GR;
11.10 typedef GrossoLocatelliPullanMc<GR> McAlg;
11.11 typedef McAlg::CliqueNodeIt CliqueIt;
11.12 @@ -68,12 +68,13 @@
11.13 GR g;
11.14 GR::NodeMap<bool> map(g);
11.15 McAlg mc(g);
11.16 - check(mc.run(max_sel, rule) == 0, "Wrong clique size");
11.17 + mc.iterationLimit(50);
11.18 + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
11.19 check(mc.cliqueSize() == 0, "Wrong clique size");
11.20 check(CliqueIt(mc) == INVALID, "Wrong CliqueNodeIt");
11.21
11.22 GR::Node u = g.addNode();
11.23 - check(mc.run(max_sel, rule) == 1, "Wrong clique size");
11.24 + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
11.25 check(mc.cliqueSize() == 1, "Wrong clique size");
11.26 mc.cliqueMap(map);
11.27 check(map[u], "Wrong clique map");
11.28 @@ -82,7 +83,7 @@
11.29 "Wrong CliqueNodeIt");
11.30
11.31 GR::Node v = g.addNode();
11.32 - check(mc.run(max_sel, rule) == 1, "Wrong clique size");
11.33 + check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
11.34 check(mc.cliqueSize() == 1, "Wrong clique size");
11.35 mc.cliqueMap(map);
11.36 check((map[u] && !map[v]) || (map[v] && !map[u]), "Wrong clique map");
11.37 @@ -90,7 +91,7 @@
11.38 check(it2 != INVALID && ++it2 == INVALID, "Wrong CliqueNodeIt");
11.39
11.40 g.addEdge(u, v);
11.41 - check(mc.run(max_sel, rule) == 2, "Wrong clique size");
11.42 + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
11.43 check(mc.cliqueSize() == 2, "Wrong clique size");
11.44 mc.cliqueMap(map);
11.45 check(map[u] && map[v], "Wrong clique map");
11.46 @@ -110,7 +111,8 @@
11.47 .run();
11.48
11.49 McAlg mc(g);
11.50 - check(mc.run(max_sel, rule) == 4, "Wrong clique size");
11.51 + mc.iterationLimit(50);
11.52 + check(mc.run(rule) == McAlg::ITERATION_LIMIT, "Wrong termination cause");
11.53 check(mc.cliqueSize() == 4, "Wrong clique size");
11.54 mc.cliqueMap(map);
11.55 for (GR::NodeIt n(g); n != INVALID; ++n) {
11.56 @@ -127,7 +129,7 @@
11.57
11.58 // Check with full graphs
11.59 template <typename Param>
11.60 -void checkMaxCliqueFullGraph(int max_sel, Param rule) {
11.61 +void checkMaxCliqueFullGraph(Param rule) {
11.62 typedef FullGraph GR;
11.63 typedef GrossoLocatelliPullanMc<FullGraph> McAlg;
11.64 typedef McAlg::CliqueNodeIt CliqueIt;
11.65 @@ -136,7 +138,7 @@
11.66 GR g(size);
11.67 GR::NodeMap<bool> map(g);
11.68 McAlg mc(g);
11.69 - check(mc.run(max_sel, rule) == size, "Wrong clique size");
11.70 + check(mc.run(rule) == McAlg::SIZE_LIMIT, "Wrong termination cause");
11.71 check(mc.cliqueSize() == size, "Wrong clique size");
11.72 mc.cliqueMap(map);
11.73 for (GR::NodeIt n(g); n != INVALID; ++n) {
11.74 @@ -150,27 +152,37 @@
11.75
11.76 // Check with grid graphs
11.77 template <typename Param>
11.78 -void checkMaxCliqueGridGraph(int max_sel, Param rule) {
11.79 +void checkMaxCliqueGridGraph(Param rule) {
11.80 GridGraph g(5, 7);
11.81 GridGraph::NodeMap<char> map(g);
11.82 GrossoLocatelliPullanMc<GridGraph> mc(g);
11.83 - check(mc.run(max_sel, rule) == 2, "Wrong clique size");
11.84 +
11.85 + mc.iterationLimit(100);
11.86 + check(mc.run(rule) == mc.ITERATION_LIMIT, "Wrong termination cause");
11.87 + check(mc.cliqueSize() == 2, "Wrong clique size");
11.88 +
11.89 + mc.stepLimit(100);
11.90 + check(mc.run(rule) == mc.STEP_LIMIT, "Wrong termination cause");
11.91 + check(mc.cliqueSize() == 2, "Wrong clique size");
11.92 +
11.93 + mc.sizeLimit(2);
11.94 + check(mc.run(rule) == mc.SIZE_LIMIT, "Wrong termination cause");
11.95 check(mc.cliqueSize() == 2, "Wrong clique size");
11.96 }
11.97
11.98
11.99 int main() {
11.100 - checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::RANDOM);
11.101 - checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
11.102 - checkMaxCliqueGeneral(50, GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
11.103 + checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::RANDOM);
11.104 + checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::DEGREE_BASED);
11.105 + checkMaxCliqueGeneral(GrossoLocatelliPullanMc<ListGraph>::PENALTY_BASED);
11.106
11.107 - checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::RANDOM);
11.108 - checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
11.109 - checkMaxCliqueFullGraph(50, GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
11.110 + checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::RANDOM);
11.111 + checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::DEGREE_BASED);
11.112 + checkMaxCliqueFullGraph(GrossoLocatelliPullanMc<FullGraph>::PENALTY_BASED);
11.113
11.114 - checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::RANDOM);
11.115 - checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
11.116 - checkMaxCliqueGridGraph(50, GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
11.117 + checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::RANDOM);
11.118 + checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::DEGREE_BASED);
11.119 + checkMaxCliqueGridGraph(GrossoLocatelliPullanMc<GridGraph>::PENALTY_BASED);
11.120
11.121 return 0;
11.122 }