# HG changeset patch # User Peter Kovacs # Date 2009-11-12 23:34:35 # Node ID 3b53491bf6436ab241c8ccf8f3c18c529174214a # Parent 22bb98ca010184543f08b8c072eaa13286422166 More options for run() in scaling MCF algorithms (#180) - Three methods can be selected and the scaling factor can be given for CostScaling. - The scaling factor can be given for CapacityScaling. diff --git a/lemon/capacity_scaling.h b/lemon/capacity_scaling.h --- a/lemon/capacity_scaling.h +++ b/lemon/capacity_scaling.h @@ -173,7 +173,7 @@ IntVector _deficit_nodes; Value _delta; - int _phase_num; + int _factor; IntVector _pred; public: @@ -513,12 +513,11 @@ /// \ref reset() is called, thus only the modified parameters /// have to be set again. See \ref reset() for examples. /// However the underlying digraph must not be modified after this - /// class have been constructed, since it copies the digraph. + /// class have been constructed, since it copies and extends the graph. /// - /// \param scaling Enable or disable capacity scaling. - /// If the maximum upper bound and/or the amount of total supply - /// is rather small, the algorithm could be slightly faster without - /// scaling. + /// \param factor The capacity scaling factor. It must be larger than + /// one to use scaling. If it is less or equal to one, then scaling + /// will be disabled. /// /// \return \c INFEASIBLE if no feasible flow exists, /// \n \c OPTIMAL if the problem has optimal solution @@ -531,8 +530,9 @@ /// these cases. /// /// \see ProblemType - ProblemType run(bool scaling = true) { - ProblemType pt = init(scaling); + ProblemType run(int factor = 4) { + _factor = factor; + ProblemType pt = init(); if (pt != OPTIMAL) return pt; return start(); } @@ -546,7 +546,7 @@ /// It is useful for multiple run() calls. If this function is not /// used, all the parameters given before are kept for the next /// \ref run() call. - /// However the underlying digraph must not be modified after this + /// However, the underlying digraph must not be modified after this /// class have been constructed, since it copies and extends the graph. /// /// For example, @@ -677,7 +677,7 @@ private: // Initialize the algorithm - ProblemType init(bool scaling) { + ProblemType init() { if (_node_num == 0) return INFEASIBLE; // Check the sum of supply values @@ -758,7 +758,7 @@ } // Initialize delta value - if (scaling) { + if (_factor > 1) { // With scaling Value max_sup = 0, max_dem = 0; for (int i = 0; i != _node_num; ++i) { @@ -770,9 +770,7 @@ if (_res_cap[j] > max_cap) max_cap = _res_cap[j]; } max_sup = std::min(std::min(max_sup, max_dem), max_cap); - _phase_num = 0; - for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) - ++_phase_num; + for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ; } else { // Without scaling _delta = 1; @@ -811,8 +809,6 @@ ProblemType startWithScaling() { // Perform capacity scaling phases int s, t; - int phase_cnt = 0; - int factor = 4; ResidualDijkstra _dijkstra(*this); while (true) { // Saturate all arcs not satisfying the optimality condition @@ -887,8 +883,7 @@ } if (_delta == 1) break; - if (++phase_cnt == _phase_num / 4) factor = 2; - _delta = _delta <= factor ? 1 : _delta / factor; + _delta = _delta <= _factor ? 1 : _delta / _factor; } return OPTIMAL; diff --git a/lemon/cost_scaling.h b/lemon/cost_scaling.h --- a/lemon/cost_scaling.h +++ b/lemon/cost_scaling.h @@ -110,6 +110,10 @@ /// be integer. /// \warning This algorithm does not support negative costs for such /// arcs that have infinite upper bound. + /// + /// \note %CostScaling provides three different internal methods, + /// from which the most efficient one is used by default. + /// For more information, see \ref Method. #ifdef DOXYGEN template #else @@ -159,6 +163,33 @@ UNBOUNDED }; + /// \brief Constants for selecting the internal method. + /// + /// Enum type containing constants for selecting the internal method + /// for the \ref run() function. + /// + /// \ref CostScaling provides three internal methods that differ mainly + /// in their base operations, which are used in conjunction with the + /// relabel operation. + /// By default, the so called \ref PARTIAL_AUGMENT + /// "Partial Augment-Relabel" method is used, which proved to be + /// the most efficient and the most robust on various test inputs. + /// However, the other methods can be selected using the \ref run() + /// function with the proper parameter. + enum Method { + /// Local push operations are used, i.e. flow is moved only on one + /// admissible arc at once. + PUSH, + /// Augment operations are used, i.e. flow is moved on admissible + /// paths from a node with excess to a node with deficit. + AUGMENT, + /// Partial augment operations are used, i.e. flow is moved on + /// admissible paths started from a node with excess, but the + /// lengths of these paths are limited. This method can be viewed + /// as a combined version of the previous two operations. + PARTIAL_AUGMENT + }; + private: TEMPLATE_DIGRAPH_TYPEDEFS(GR); @@ -505,13 +536,12 @@ /// that have been given are kept for the next call, unless /// \ref reset() is called, thus only the modified parameters /// have to be set again. See \ref reset() for examples. - /// However the underlying digraph must not be modified after this - /// class have been constructed, since it copies the digraph. + /// However, the underlying digraph must not be modified after this + /// class have been constructed, since it copies and extends the graph. /// - /// \param partial_augment By default the algorithm performs - /// partial augment and relabel operations in the cost scaling - /// phases. Set this parameter to \c false for using local push and - /// relabel operations instead. + /// \param method The internal method that will be used in the + /// algorithm. For more information, see \ref Method. + /// \param factor The cost scaling factor. It must be larger than one. /// /// \return \c INFEASIBLE if no feasible flow exists, /// \n \c OPTIMAL if the problem has optimal solution @@ -523,11 +553,12 @@ /// bounded over the feasible flows, but this algroithm cannot handle /// these cases. /// - /// \see ProblemType - ProblemType run(bool partial_augment = true) { + /// \see ProblemType, Method + ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { + _alpha = factor; ProblemType pt = init(); if (pt != OPTIMAL) return pt; - start(partial_augment); + start(method); return OPTIMAL; } @@ -681,9 +712,6 @@ ProblemType init() { if (_res_node_num == 0) return INFEASIBLE; - // Scaling factor - _alpha = 8; - // Check the sum of supply values _sum_supply = 0; for (int i = 0; i != _root; ++i) { @@ -817,12 +845,21 @@ } // Execute the algorithm and transform the results - void start(bool partial_augment) { + void start(Method method) { + // Maximum path length for partial augment + const int MAX_PATH_LENGTH = 4; + // Execute the algorithm - if (partial_augment) { - startPartialAugment(); - } else { - startPushRelabel(); + switch (method) { + case PUSH: + startPush(); + break; + case AUGMENT: + startAugment(); + break; + case PARTIAL_AUGMENT: + startAugment(MAX_PATH_LENGTH); + break; } // Compute node potentials for the original costs @@ -851,14 +888,11 @@ } } - /// Execute the algorithm performing partial augmentation and - /// relabel operations - void startPartialAugment() { + /// Execute the algorithm performing augment and relabel operations + void startAugment(int max_length = std::numeric_limits::max()) { // Paramters for heuristics const int BF_HEURISTIC_EPSILON_BOUND = 1000; const int BF_HEURISTIC_BOUND_FACTOR = 3; - // Maximum augment path length - const int MAX_PATH_LENGTH = 4; // Perform cost scaling phases IntVector pred_arc(_res_node_num); @@ -925,7 +959,7 @@ // Find an augmenting path from the start node int tip = start; while (_excess[tip] >= 0 && - int(path_nodes.size()) <= MAX_PATH_LENGTH) { + int(path_nodes.size()) <= max_length) { int u; LargeCost min_red_cost, rc; int last_out = _sum_supply < 0 ? @@ -984,7 +1018,7 @@ } /// Execute the algorithm performing push and relabel operations - void startPushRelabel() { + void startPush() { // Paramters for heuristics const int BF_HEURISTIC_EPSILON_BOUND = 1000; const int BF_HEURISTIC_BOUND_FACTOR = 3;