1.1 --- a/lemon/cost_scaling.h Thu Nov 12 23:30:45 2009 +0100
1.2 +++ b/lemon/cost_scaling.h Thu Nov 12 23:34:35 2009 +0100
1.3 @@ -110,6 +110,10 @@
1.4 /// be integer.
1.5 /// \warning This algorithm does not support negative costs for such
1.6 /// arcs that have infinite upper bound.
1.7 + ///
1.8 + /// \note %CostScaling provides three different internal methods,
1.9 + /// from which the most efficient one is used by default.
1.10 + /// For more information, see \ref Method.
1.11 #ifdef DOXYGEN
1.12 template <typename GR, typename V, typename C, typename TR>
1.13 #else
1.14 @@ -159,6 +163,33 @@
1.15 UNBOUNDED
1.16 };
1.17
1.18 + /// \brief Constants for selecting the internal method.
1.19 + ///
1.20 + /// Enum type containing constants for selecting the internal method
1.21 + /// for the \ref run() function.
1.22 + ///
1.23 + /// \ref CostScaling provides three internal methods that differ mainly
1.24 + /// in their base operations, which are used in conjunction with the
1.25 + /// relabel operation.
1.26 + /// By default, the so called \ref PARTIAL_AUGMENT
1.27 + /// "Partial Augment-Relabel" method is used, which proved to be
1.28 + /// the most efficient and the most robust on various test inputs.
1.29 + /// However, the other methods can be selected using the \ref run()
1.30 + /// function with the proper parameter.
1.31 + enum Method {
1.32 + /// Local push operations are used, i.e. flow is moved only on one
1.33 + /// admissible arc at once.
1.34 + PUSH,
1.35 + /// Augment operations are used, i.e. flow is moved on admissible
1.36 + /// paths from a node with excess to a node with deficit.
1.37 + AUGMENT,
1.38 + /// Partial augment operations are used, i.e. flow is moved on
1.39 + /// admissible paths started from a node with excess, but the
1.40 + /// lengths of these paths are limited. This method can be viewed
1.41 + /// as a combined version of the previous two operations.
1.42 + PARTIAL_AUGMENT
1.43 + };
1.44 +
1.45 private:
1.46
1.47 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
1.48 @@ -505,13 +536,12 @@
1.49 /// that have been given are kept for the next call, unless
1.50 /// \ref reset() is called, thus only the modified parameters
1.51 /// have to be set again. See \ref reset() for examples.
1.52 - /// However the underlying digraph must not be modified after this
1.53 - /// class have been constructed, since it copies the digraph.
1.54 + /// However, the underlying digraph must not be modified after this
1.55 + /// class have been constructed, since it copies and extends the graph.
1.56 ///
1.57 - /// \param partial_augment By default the algorithm performs
1.58 - /// partial augment and relabel operations in the cost scaling
1.59 - /// phases. Set this parameter to \c false for using local push and
1.60 - /// relabel operations instead.
1.61 + /// \param method The internal method that will be used in the
1.62 + /// algorithm. For more information, see \ref Method.
1.63 + /// \param factor The cost scaling factor. It must be larger than one.
1.64 ///
1.65 /// \return \c INFEASIBLE if no feasible flow exists,
1.66 /// \n \c OPTIMAL if the problem has optimal solution
1.67 @@ -523,11 +553,12 @@
1.68 /// bounded over the feasible flows, but this algroithm cannot handle
1.69 /// these cases.
1.70 ///
1.71 - /// \see ProblemType
1.72 - ProblemType run(bool partial_augment = true) {
1.73 + /// \see ProblemType, Method
1.74 + ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) {
1.75 + _alpha = factor;
1.76 ProblemType pt = init();
1.77 if (pt != OPTIMAL) return pt;
1.78 - start(partial_augment);
1.79 + start(method);
1.80 return OPTIMAL;
1.81 }
1.82
1.83 @@ -681,9 +712,6 @@
1.84 ProblemType init() {
1.85 if (_res_node_num == 0) return INFEASIBLE;
1.86
1.87 - // Scaling factor
1.88 - _alpha = 8;
1.89 -
1.90 // Check the sum of supply values
1.91 _sum_supply = 0;
1.92 for (int i = 0; i != _root; ++i) {
1.93 @@ -817,12 +845,21 @@
1.94 }
1.95
1.96 // Execute the algorithm and transform the results
1.97 - void start(bool partial_augment) {
1.98 + void start(Method method) {
1.99 + // Maximum path length for partial augment
1.100 + const int MAX_PATH_LENGTH = 4;
1.101 +
1.102 // Execute the algorithm
1.103 - if (partial_augment) {
1.104 - startPartialAugment();
1.105 - } else {
1.106 - startPushRelabel();
1.107 + switch (method) {
1.108 + case PUSH:
1.109 + startPush();
1.110 + break;
1.111 + case AUGMENT:
1.112 + startAugment();
1.113 + break;
1.114 + case PARTIAL_AUGMENT:
1.115 + startAugment(MAX_PATH_LENGTH);
1.116 + break;
1.117 }
1.118
1.119 // Compute node potentials for the original costs
1.120 @@ -851,14 +888,11 @@
1.121 }
1.122 }
1.123
1.124 - /// Execute the algorithm performing partial augmentation and
1.125 - /// relabel operations
1.126 - void startPartialAugment() {
1.127 + /// Execute the algorithm performing augment and relabel operations
1.128 + void startAugment(int max_length = std::numeric_limits<int>::max()) {
1.129 // Paramters for heuristics
1.130 const int BF_HEURISTIC_EPSILON_BOUND = 1000;
1.131 const int BF_HEURISTIC_BOUND_FACTOR = 3;
1.132 - // Maximum augment path length
1.133 - const int MAX_PATH_LENGTH = 4;
1.134
1.135 // Perform cost scaling phases
1.136 IntVector pred_arc(_res_node_num);
1.137 @@ -925,7 +959,7 @@
1.138 // Find an augmenting path from the start node
1.139 int tip = start;
1.140 while (_excess[tip] >= 0 &&
1.141 - int(path_nodes.size()) <= MAX_PATH_LENGTH) {
1.142 + int(path_nodes.size()) <= max_length) {
1.143 int u;
1.144 LargeCost min_red_cost, rc;
1.145 int last_out = _sum_supply < 0 ?
1.146 @@ -984,7 +1018,7 @@
1.147 }
1.148
1.149 /// Execute the algorithm performing push and relabel operations
1.150 - void startPushRelabel() {
1.151 + void startPush() {
1.152 // Paramters for heuristics
1.153 const int BF_HEURISTIC_EPSILON_BOUND = 1000;
1.154 const int BF_HEURISTIC_BOUND_FACTOR = 3;