Changeset 810:3b53491bf643 in lemon-main for lemon/cost_scaling.h

Timestamp:

11/12/09 23:34:35 (15 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?.

File:

• lemon/cost_scaling.h (modified) (9 diffs)

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;