# Changeset 876:3b53491bf643 in lemon for lemon

Ignore:
Timestamp:
11/12/09 23:34:35 (10 years ago)
Branch:
default
Phase:
public
Rebase:
31306464373530663736663634663865303635326136663934636335303533383063623764626530
Message:

More options for run() in scaling MCF algorithms (#180)

Location:
lemon
Files:
2 edited

Unmodified
Removed
• ## lemon/capacity_scaling.h

 r873 Value _delta; int _phase_num; int _factor; IntVector _pred; /// 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. /// /// \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. /// class have been constructed, since it copies and extends the graph. /// /// \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, /// /// \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(); /// 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. /// // Initialize the algorithm ProblemType init(bool scaling) { ProblemType init() { if (_node_num == 0) return INFEASIBLE; // Initialize delta value if (scaling) { if (_factor > 1) { // With scaling Value max_sup = 0, max_dem = 0; } 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 // Perform capacity scaling phases int s, t; int phase_cnt = 0; int factor = 4; ResidualDijkstra _dijkstra(*this); while (true) { if (_delta == 1) break; if (++phase_cnt == _phase_num / 4) factor = 2; _delta = _delta <= factor ? 1 : _delta / factor; _delta = _delta <= _factor ? 1 : _delta / _factor; }
• ## lemon/cost_scaling.h

 r875 /// \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 }; /// \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: /// \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. /// /// \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. /// However, the underlying digraph must not be modified after this /// class have been constructed, since it copies and extends the graph. /// /// \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, /// 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; } ProblemType init() { if (_res_node_num == 0) return INFEASIBLE; // Scaling factor _alpha = 8; // Check the sum of supply values // 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; } } /// 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 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; /// Execute the algorithm performing push and relabel operations void startPushRelabel() { void startPush() { // Paramters for heuristics const int BF_HEURISTIC_EPSILON_BOUND = 1000;
Note: See TracChangeset for help on using the changeset viewer.