1.1 --- a/lemon/capacity_scaling.h Thu Nov 12 23:30:45 2009 +0100
1.2 +++ b/lemon/capacity_scaling.h Thu Nov 12 23:34:35 2009 +0100
1.3 @@ -173,7 +173,7 @@
1.4 IntVector _deficit_nodes;
1.5
1.6 Value _delta;
1.7 - int _phase_num;
1.8 + int _factor;
1.9 IntVector _pred;
1.10
1.11 public:
1.12 @@ -513,12 +513,11 @@
1.13 /// \ref reset() is called, thus only the modified parameters
1.14 /// have to be set again. See \ref reset() for examples.
1.15 /// However the underlying digraph must not be modified after this
1.16 - /// class have been constructed, since it copies the digraph.
1.17 + /// class have been constructed, since it copies and extends the graph.
1.18 ///
1.19 - /// \param scaling Enable or disable capacity scaling.
1.20 - /// If the maximum upper bound and/or the amount of total supply
1.21 - /// is rather small, the algorithm could be slightly faster without
1.22 - /// scaling.
1.23 + /// \param factor The capacity scaling factor. It must be larger than
1.24 + /// one to use scaling. If it is less or equal to one, then scaling
1.25 + /// will be disabled.
1.26 ///
1.27 /// \return \c INFEASIBLE if no feasible flow exists,
1.28 /// \n \c OPTIMAL if the problem has optimal solution
1.29 @@ -531,8 +530,9 @@
1.30 /// these cases.
1.31 ///
1.32 /// \see ProblemType
1.33 - ProblemType run(bool scaling = true) {
1.34 - ProblemType pt = init(scaling);
1.35 + ProblemType run(int factor = 4) {
1.36 + _factor = factor;
1.37 + ProblemType pt = init();
1.38 if (pt != OPTIMAL) return pt;
1.39 return start();
1.40 }
1.41 @@ -546,7 +546,7 @@
1.42 /// It is useful for multiple run() calls. If this function is not
1.43 /// used, all the parameters given before are kept for the next
1.44 /// \ref run() call.
1.45 - /// However the underlying digraph must not be modified after this
1.46 + /// However, the underlying digraph must not be modified after this
1.47 /// class have been constructed, since it copies and extends the graph.
1.48 ///
1.49 /// For example,
1.50 @@ -677,7 +677,7 @@
1.51 private:
1.52
1.53 // Initialize the algorithm
1.54 - ProblemType init(bool scaling) {
1.55 + ProblemType init() {
1.56 if (_node_num == 0) return INFEASIBLE;
1.57
1.58 // Check the sum of supply values
1.59 @@ -758,7 +758,7 @@
1.60 }
1.61
1.62 // Initialize delta value
1.63 - if (scaling) {
1.64 + if (_factor > 1) {
1.65 // With scaling
1.66 Value max_sup = 0, max_dem = 0;
1.67 for (int i = 0; i != _node_num; ++i) {
1.68 @@ -770,9 +770,7 @@
1.69 if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
1.70 }
1.71 max_sup = std::min(std::min(max_sup, max_dem), max_cap);
1.72 - _phase_num = 0;
1.73 - for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2)
1.74 - ++_phase_num;
1.75 + for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;
1.76 } else {
1.77 // Without scaling
1.78 _delta = 1;
1.79 @@ -811,8 +809,6 @@
1.80 ProblemType startWithScaling() {
1.81 // Perform capacity scaling phases
1.82 int s, t;
1.83 - int phase_cnt = 0;
1.84 - int factor = 4;
1.85 ResidualDijkstra _dijkstra(*this);
1.86 while (true) {
1.87 // Saturate all arcs not satisfying the optimality condition
1.88 @@ -887,8 +883,7 @@
1.89 }
1.90
1.91 if (_delta == 1) break;
1.92 - if (++phase_cnt == _phase_num / 4) factor = 2;
1.93 - _delta = _delta <= factor ? 1 : _delta / factor;
1.94 + _delta = _delta <= _factor ? 1 : _delta / _factor;
1.95 }
1.96
1.97 return OPTIMAL;
2.1 --- a/lemon/cost_scaling.h Thu Nov 12 23:30:45 2009 +0100
2.2 +++ b/lemon/cost_scaling.h Thu Nov 12 23:34:35 2009 +0100
2.3 @@ -110,6 +110,10 @@
2.4 /// be integer.
2.5 /// \warning This algorithm does not support negative costs for such
2.6 /// arcs that have infinite upper bound.
2.7 + ///
2.8 + /// \note %CostScaling provides three different internal methods,
2.9 + /// from which the most efficient one is used by default.
2.10 + /// For more information, see \ref Method.
2.11 #ifdef DOXYGEN
2.12 template <typename GR, typename V, typename C, typename TR>
2.13 #else
2.14 @@ -159,6 +163,33 @@
2.15 UNBOUNDED
2.16 };
2.17
2.18 + /// \brief Constants for selecting the internal method.
2.19 + ///
2.20 + /// Enum type containing constants for selecting the internal method
2.21 + /// for the \ref run() function.
2.22 + ///
2.23 + /// \ref CostScaling provides three internal methods that differ mainly
2.24 + /// in their base operations, which are used in conjunction with the
2.25 + /// relabel operation.
2.26 + /// By default, the so called \ref PARTIAL_AUGMENT
2.27 + /// "Partial Augment-Relabel" method is used, which proved to be
2.28 + /// the most efficient and the most robust on various test inputs.
2.29 + /// However, the other methods can be selected using the \ref run()
2.30 + /// function with the proper parameter.
2.31 + enum Method {
2.32 + /// Local push operations are used, i.e. flow is moved only on one
2.33 + /// admissible arc at once.
2.34 + PUSH,
2.35 + /// Augment operations are used, i.e. flow is moved on admissible
2.36 + /// paths from a node with excess to a node with deficit.
2.37 + AUGMENT,
2.38 + /// Partial augment operations are used, i.e. flow is moved on
2.39 + /// admissible paths started from a node with excess, but the
2.40 + /// lengths of these paths are limited. This method can be viewed
2.41 + /// as a combined version of the previous two operations.
2.42 + PARTIAL_AUGMENT
2.43 + };
2.44 +
2.45 private:
2.46
2.47 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
2.48 @@ -505,13 +536,12 @@
2.49 /// that have been given are kept for the next call, unless
2.50 /// \ref reset() is called, thus only the modified parameters
2.51 /// have to be set again. See \ref reset() for examples.
2.52 - /// However the underlying digraph must not be modified after this
2.53 - /// class have been constructed, since it copies the digraph.
2.54 + /// However, the underlying digraph must not be modified after this
2.55 + /// class have been constructed, since it copies and extends the graph.
2.56 ///
2.57 - /// \param partial_augment By default the algorithm performs
2.58 - /// partial augment and relabel operations in the cost scaling
2.59 - /// phases. Set this parameter to \c false for using local push and
2.60 - /// relabel operations instead.
2.61 + /// \param method The internal method that will be used in the
2.62 + /// algorithm. For more information, see \ref Method.
2.63 + /// \param factor The cost scaling factor. It must be larger than one.
2.64 ///
2.65 /// \return \c INFEASIBLE if no feasible flow exists,
2.66 /// \n \c OPTIMAL if the problem has optimal solution
2.67 @@ -523,11 +553,12 @@
2.68 /// bounded over the feasible flows, but this algroithm cannot handle
2.69 /// these cases.
2.70 ///
2.71 - /// \see ProblemType
2.72 - ProblemType run(bool partial_augment = true) {
2.73 + /// \see ProblemType, Method
2.74 + ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
2.75 + _alpha = factor;
2.76 ProblemType pt = init();
2.77 if (pt != OPTIMAL) return pt;
2.78 - start(partial_augment);
2.79 + start(method);
2.80 return OPTIMAL;
2.81 }
2.82
2.83 @@ -681,9 +712,6 @@
2.84 ProblemType init() {
2.85 if (_res_node_num == 0) return INFEASIBLE;
2.86
2.87 - // Scaling factor
2.88 - _alpha = 8;
2.89 -
2.90 // Check the sum of supply values
2.91 _sum_supply = 0;
2.92 for (int i = 0; i != _root; ++i) {
2.93 @@ -817,12 +845,21 @@
2.94 }
2.95
2.96 // Execute the algorithm and transform the results
2.97 - void start(bool partial_augment) {
2.98 + void start(Method method) {
2.99 + // Maximum path length for partial augment
2.100 + const int MAX_PATH_LENGTH = 4;
2.101 +
2.102 // Execute the algorithm
2.103 - if (partial_augment) {
2.104 - startPartialAugment();
2.105 - } else {
2.106 - startPushRelabel();
2.107 + switch (method) {
2.108 + case PUSH:
2.109 + startPush();
2.110 + break;
2.111 + case AUGMENT:
2.112 + startAugment();
2.113 + break;
2.114 + case PARTIAL_AUGMENT:
2.115 + startAugment(MAX_PATH_LENGTH);
2.116 + break;
2.117 }
2.118
2.119 // Compute node potentials for the original costs
2.120 @@ -851,14 +888,11 @@
2.121 }
2.122 }
2.123
2.124 - /// Execute the algorithm performing partial augmentation and
2.125 - /// relabel operations
2.126 - void startPartialAugment() {
2.127 + /// Execute the algorithm performing augment and relabel operations
2.128 + void startAugment(int max_length = std::numeric_limits<int>::max()) {
2.129 // Paramters for heuristics
2.130 const int BF_HEURISTIC_EPSILON_BOUND = 1000;
2.131 const int BF_HEURISTIC_BOUND_FACTOR = 3;
2.132 - // Maximum augment path length
2.133 - const int MAX_PATH_LENGTH = 4;
2.134
2.135 // Perform cost scaling phases
2.136 IntVector pred_arc(_res_node_num);
2.137 @@ -925,7 +959,7 @@
2.138 // Find an augmenting path from the start node
2.139 int tip = start;
2.140 while (_excess[tip] >= 0 &&
2.141 - int(path_nodes.size()) <= MAX_PATH_LENGTH) {
2.142 + int(path_nodes.size()) <= max_length) {
2.143 int u;
2.144 LargeCost min_red_cost, rc;
2.145 int last_out = _sum_supply < 0 ?
2.146 @@ -984,7 +1018,7 @@
2.147 }
2.148
2.149 /// Execute the algorithm performing push and relabel operations
2.150 - void startPushRelabel() {
2.151 + void startPush() {
2.152 // Paramters for heuristics
2.153 const int BF_HEURISTIC_EPSILON_BOUND = 1000;
2.154 const int BF_HEURISTIC_BOUND_FACTOR = 3;