Changeset 877:141f9c0db4a3 in lemon-1.2 for lemon/cost_scaling.h

Timestamp:

03/06/10 15:35:12 (14 years ago)

Author:

Alpar Juttner <alpar@…>

Branch:

default

Children:

878:f802439d2b58, 880:38213abd2911, 909:f112c18bc304

Phase:

public

Message:

Unify the sources (#339)

File:

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

lemon/cost_scaling.h

@@ -1 @@
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
  *
- * This file is a part of LEMON, a generic C++ optimization library
+ * This file is a part of LEMON, a generic C++ optimization library.
  *
- * Copyright (C) 2003-2008
+ * Copyright (C) 2003-2010
  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -93 +93 @@
   /// push/augment and relabel operations for finding a \ref min_cost_flow
   /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
-  /// \ref goldberg97efficient, \ref bunnagel98efficient. 
+  /// \ref goldberg97efficient, \ref bunnagel98efficient.
   /// It is a highly efficient primal-dual solution method, which
   /// can be viewed as the generalization of the \ref Preflow
@@ -190 +190 @@
       /// paths from a node with excess to a node with deficit.
       AUGMENT,
-      /// Partial augment operations are used, i.e. flow is moved on 
+      /// 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
@@ -209 +209 @@
 
   private:
-  
+
     template <typename KT, typename VT>
     class StaticVectorMap {
@@ -215 +215 @@
       typedef KT Key;
       typedef VT Value;
-      
+
       StaticVectorMap(std::vector<Value>& v) : _v(v) {}
-      
+
       const Value& operator[](const Key& key) const {
         return _v[StaticDigraph::id(key)];
@@ -225 +225 @@
         return _v[StaticDigraph::id(key)];
       }
-      
+
       void set(const Key& key, const Value& val) {
         _v[StaticDigraph::id(key)] = val;
@@ -284 +284 @@
     IntVector _rank;
     int _max_rank;
-  
+
     // Data for a StaticDigraph structure
     typedef std::pair<int, int> IntPair;
@@ -292 +292 @@
     LargeCostArcMap _cost_map;
     LargeCostNodeMap _pi_map;
-  
+
   public:
-  
+
     /// \brief Constant for infinite upper bounds (capacities).
     ///
@@ -349 +349 @@
       LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
         "The cost type of CostScaling must be signed");
-      
+
       // Reset data structures
       reset();
@@ -465 +465 @@
       return *this;
     }
-    
+
     /// @}
 
@@ -567 +567 @@
         _scost[j] = 0;
         _scost[_reverse[j]] = 0;
-      }      
+      }
       _have_lower = false;
       return *this;
@@ -602 +602 @@
       _scost.resize(_res_arc_num);
       _supply.resize(_res_node_num);
-      
+
       _res_cap.resize(_res_arc_num);
       _cost.resize(_res_arc_num);
@@ -650 +650 @@
         _reverse[bi] = fi;
       }
-      
+
       // Reset parameters
       resetParams();
@@ -759 +759 @@
       }
       if (_sum_supply > 0) return INFEASIBLE;
-      
+
 
       // Initialize vectors
@@ -766 +766 @@
         _excess[i] = _supply[i];
       }
-      
+
       // Remove infinite upper bounds and check negative arcs
       const Value MAX = std::numeric_limits<Value>::max();
@@ -886 +886 @@
         }
       }
-      
+
       return OPTIMAL;
     }
@@ -895 +895 @@
       const int MAX_PATH_LENGTH = 4;
 
-      // Initialize data structures for buckets      
+      // Initialize data structures for buckets
       _max_rank = _alpha * _res_node_num;
       _buckets.resize(_max_rank);
@@ -901 +901 @@
       _bucket_prev.resize(_res_node_num + 1);
       _rank.resize(_res_node_num + 1);
-  
+
       // Execute the algorithm
       switch (method) {
@@ -940 +940 @@
       }
     }
-    
+
     // Initialize a cost scaling phase
     void initPhase() {
@@ -958 +958 @@
         }
       }
-      
+
       // Find active nodes (i.e. nodes with positive excess)
       for (int u = 0; u != _res_node_num; ++u) {
@@ -969 +969 @@
       }
     }
-    
+
     // Early termination heuristic
     bool earlyTermination() {
@@ -999 +999 @@
     void globalUpdate() {
       int bucket_end = _root + 1;
-    
+
       // Initialize buckets
       for (int r = 0; r != _max_rank; ++r) {
@@ -1025 +1025 @@
           int u = _buckets[r];
           _buckets[r] = _bucket_next[u];
-          
+
           // Search the incomming arcs of u
           LargeCost pi_u = _pi[u];
@@ -1040 +1040 @@
                 if (nrc < LargeCost(_max_rank))
                   new_rank_v = r + 1 + int(nrc);
-                  
+
                 // Change the rank of v
                 if (new_rank_v < old_rank_v) {
                   _rank[v] = new_rank_v;
                   _next_out[v] = _first_out[v];
-                  
+
                   // Remove v from its old bucket
                   if (old_rank_v < _max_rank) {
@@ -1055 +1055 @@
                     }
                   }
-                  
+
                   // Insert v to its new bucket
                   _bucket_next[v] = _buckets[new_rank_v];
@@ -1073 +1073 @@
         if (total_excess <= 0) break;
       }
-      
+
       // Relabel nodes
       for (int u = 0; u != _res_node_num; ++u) {
@@ -1093 +1093 @@
         (_res_node_num + _sup_node_num * _sup_node_num));
       int next_update_limit = global_update_freq;
-      
+
       int relabel_cnt = 0;
-      
+
       // Perform cost scaling phases
       std::vector<int> path;
@@ -1105 +1105 @@
           if (earlyTermination()) break;
         }
-        
+
         // Initialize current phase
         initPhase();
-        
+
         // Perform partial augment and relabel operations
         while (true) {
@@ -1197 +1197 @@
 
       int relabel_cnt = 0;
-      
+
       // Perform cost scaling phases
       BoolVector hyper(_res_node_num, false);
@@ -1208 +1208 @@
           if (earlyTermination()) break;
         }
-        
+
         // Initialize current phase
         initPhase();
@@ -1223 +1223 @@
           last_out = _first_out[n+1];
           pi_n = _pi[n];
-          
+
           // Perform push operations if there are admissible arcs
           if (_excess[n] > 0) {
@@ -1237 +1237 @@
                 LargeCost pi_t = _pi[t];
                 for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
-                  if (_res_cap[ta] > 0 && 
+                  if (_res_cap[ta] > 0 &&
                       _cost[ta] + pi_t - _pi[_target[ta]] < 0)
                     ahead += _res_cap[ta];
@@ -1288 +1288 @@
             ++relabel_cnt;
           }
-        
+
           // Remove nodes that are not active nor hyper
         remove_nodes:
@@ -1296 +1296 @@
             _active_nodes.pop_front();
           }
-          
+
           // Global update heuristic
           if (relabel_cnt >= next_update_limit) {