# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1258065275 -3600
# 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 -r 22bb98ca0101 -r 3b53491bf643 lemon/capacity_scaling.h
--- a/lemon/capacity_scaling.h Thu Nov 12 23:30:45 2009 +0100
+++ b/lemon/capacity_scaling.h Thu Nov 12 23:34:35 2009 +0100
@@ -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 -r 22bb98ca0101 -r 3b53491bf643 lemon/cost_scaling.h
--- a/lemon/cost_scaling.h Thu Nov 12 23:30:45 2009 +0100
+++ b/lemon/cost_scaling.h Thu Nov 12 23:34:35 2009 +0100
@@ -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 <typename GR, typename V, typename C, typename TR>
#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<int>::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;