Changeset 810:3b53491bf643 in lemon-main for lemon

Timestamp:

11/12/09 23:34:35 (14 years ago)

Author:

Peter Kovacs <kpeter@…>

Branch:

default

Phase:

public

Rebase:

31306464373530663736663634663865303635326136663934636335303533383063623764626530

Message:

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?.

Location:

lemon

Files:

• capacity_scaling.h (modified) (9 diffs)
• cost_scaling.h (modified) (9 diffs)

lemon/capacity_scaling.h

@@ -174 +174 @@
 
     Value _delta;
-    int _phase_num;
+    int _factor;
     IntVector _pred;
 
@@ -514 +514 @@
     /// 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,
@@ -532 +531 @@
     ///
     /// \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();
@@ -547 +547 @@
     /// 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.
     ///
@@ -678 +678 @@
 
     // Initialize the algorithm
-    ProblemType init(bool scaling) {
+    ProblemType init() {
       if (_node_num == 0) return INFEASIBLE;
 
@@ -759 +759 @@
 
       // Initialize delta value
-      if (scaling) {
+      if (_factor > 1) {
         // With scaling
         Value max_sup = 0, max_dem = 0;
@@ -771 +771 @@
         }
         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
@@ -812 +810 @@
       // Perform capacity scaling phases
       int s, t;
-      int phase_cnt = 0;
-      int factor = 4;
       ResidualDijkstra _dijkstra(*this);
       while (true) {
@@ -888 +884 @@
 
         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

@@ -111 +111 @@
   /// \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>
@@ -160 +164 @@
     };
 
+    /// \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:
 
@@ -506 +537 @@
     /// \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,
@@ -524 +554 @@
     /// 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 +712 @@
     ProblemType init() {
       if (_res_node_num == 0) return INFEASIBLE;
-
-      // Scaling factor
-      _alpha = 8;
 
       // Check the sum of supply values
@@ -818 +846 @@
 
     // 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;
       }
 
@@ -852 +889 @@
     }
 
-    /// 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
@@ -926 +960 @@
           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;
@@ -985 +1019 @@
 
     /// Execute the algorithm performing push and relabel operations
-    void startPushRelabel() {
+    void startPush() {
       // Paramters for heuristics
       const int BF_HEURISTIC_EPSILON_BOUND = 1000;