COIN-OR::LEMON - Graph Library

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


Ignore:
Timestamp:
03/06/10 15:35:12 (10 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
878:f802439d2b58, 880:38213abd2911, 909:f112c18bc304
Phase:
public
Message:

Unify the sources (#339)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cost_scaling.h

    r863 r877  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2008
     5 * Copyright (C) 2003-2010
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9393  /// push/augment and relabel operations for finding a \ref min_cost_flow
    9494  /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
    95   /// \ref goldberg97efficient, \ref bunnagel98efficient. 
     95  /// \ref goldberg97efficient, \ref bunnagel98efficient.
    9696  /// It is a highly efficient primal-dual solution method, which
    9797  /// can be viewed as the generalization of the \ref Preflow
     
    190190      /// paths from a node with excess to a node with deficit.
    191191      AUGMENT,
    192       /// Partial augment operations are used, i.e. flow is moved on 
     192      /// Partial augment operations are used, i.e. flow is moved on
    193193      /// admissible paths started from a node with excess, but the
    194194      /// lengths of these paths are limited. This method can be viewed
     
    209209
    210210  private:
    211  
     211
    212212    template <typename KT, typename VT>
    213213    class StaticVectorMap {
     
    215215      typedef KT Key;
    216216      typedef VT Value;
    217      
     217
    218218      StaticVectorMap(std::vector<Value>& v) : _v(v) {}
    219      
     219
    220220      const Value& operator[](const Key& key) const {
    221221        return _v[StaticDigraph::id(key)];
     
    225225        return _v[StaticDigraph::id(key)];
    226226      }
    227      
     227
    228228      void set(const Key& key, const Value& val) {
    229229        _v[StaticDigraph::id(key)] = val;
     
    284284    IntVector _rank;
    285285    int _max_rank;
    286  
     286
    287287    // Data for a StaticDigraph structure
    288288    typedef std::pair<int, int> IntPair;
     
    292292    LargeCostArcMap _cost_map;
    293293    LargeCostNodeMap _pi_map;
    294  
     294
    295295  public:
    296  
     296
    297297    /// \brief Constant for infinite upper bounds (capacities).
    298298    ///
     
    349349      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
    350350        "The cost type of CostScaling must be signed");
    351      
     351
    352352      // Reset data structures
    353353      reset();
     
    465465      return *this;
    466466    }
    467    
     467
    468468    /// @}
    469469
     
    567567        _scost[j] = 0;
    568568        _scost[_reverse[j]] = 0;
    569       }     
     569      }
    570570      _have_lower = false;
    571571      return *this;
     
    602602      _scost.resize(_res_arc_num);
    603603      _supply.resize(_res_node_num);
    604      
     604
    605605      _res_cap.resize(_res_arc_num);
    606606      _cost.resize(_res_arc_num);
     
    650650        _reverse[bi] = fi;
    651651      }
    652      
     652
    653653      // Reset parameters
    654654      resetParams();
     
    759759      }
    760760      if (_sum_supply > 0) return INFEASIBLE;
    761      
     761
    762762
    763763      // Initialize vectors
     
    766766        _excess[i] = _supply[i];
    767767      }
    768      
     768
    769769      // Remove infinite upper bounds and check negative arcs
    770770      const Value MAX = std::numeric_limits<Value>::max();
     
    886886        }
    887887      }
    888      
     888
    889889      return OPTIMAL;
    890890    }
     
    895895      const int MAX_PATH_LENGTH = 4;
    896896
    897       // Initialize data structures for buckets     
     897      // Initialize data structures for buckets
    898898      _max_rank = _alpha * _res_node_num;
    899899      _buckets.resize(_max_rank);
     
    901901      _bucket_prev.resize(_res_node_num + 1);
    902902      _rank.resize(_res_node_num + 1);
    903  
     903
    904904      // Execute the algorithm
    905905      switch (method) {
     
    940940      }
    941941    }
    942    
     942
    943943    // Initialize a cost scaling phase
    944944    void initPhase() {
     
    958958        }
    959959      }
    960      
     960
    961961      // Find active nodes (i.e. nodes with positive excess)
    962962      for (int u = 0; u != _res_node_num; ++u) {
     
    969969      }
    970970    }
    971    
     971
    972972    // Early termination heuristic
    973973    bool earlyTermination() {
     
    999999    void globalUpdate() {
    10001000      int bucket_end = _root + 1;
    1001    
     1001
    10021002      // Initialize buckets
    10031003      for (int r = 0; r != _max_rank; ++r) {
     
    10251025          int u = _buckets[r];
    10261026          _buckets[r] = _bucket_next[u];
    1027          
     1027
    10281028          // Search the incomming arcs of u
    10291029          LargeCost pi_u = _pi[u];
     
    10401040                if (nrc < LargeCost(_max_rank))
    10411041                  new_rank_v = r + 1 + int(nrc);
    1042                  
     1042
    10431043                // Change the rank of v
    10441044                if (new_rank_v < old_rank_v) {
    10451045                  _rank[v] = new_rank_v;
    10461046                  _next_out[v] = _first_out[v];
    1047                  
     1047
    10481048                  // Remove v from its old bucket
    10491049                  if (old_rank_v < _max_rank) {
     
    10551055                    }
    10561056                  }
    1057                  
     1057
    10581058                  // Insert v to its new bucket
    10591059                  _bucket_next[v] = _buckets[new_rank_v];
     
    10731073        if (total_excess <= 0) break;
    10741074      }
    1075      
     1075
    10761076      // Relabel nodes
    10771077      for (int u = 0; u != _res_node_num; ++u) {
     
    10931093        (_res_node_num + _sup_node_num * _sup_node_num));
    10941094      int next_update_limit = global_update_freq;
    1095      
     1095
    10961096      int relabel_cnt = 0;
    1097      
     1097
    10981098      // Perform cost scaling phases
    10991099      std::vector<int> path;
     
    11051105          if (earlyTermination()) break;
    11061106        }
    1107        
     1107
    11081108        // Initialize current phase
    11091109        initPhase();
    1110        
     1110
    11111111        // Perform partial augment and relabel operations
    11121112        while (true) {
     
    11971197
    11981198      int relabel_cnt = 0;
    1199      
     1199
    12001200      // Perform cost scaling phases
    12011201      BoolVector hyper(_res_node_num, false);
     
    12081208          if (earlyTermination()) break;
    12091209        }
    1210        
     1210
    12111211        // Initialize current phase
    12121212        initPhase();
     
    12231223          last_out = _first_out[n+1];
    12241224          pi_n = _pi[n];
    1225          
     1225
    12261226          // Perform push operations if there are admissible arcs
    12271227          if (_excess[n] > 0) {
     
    12371237                LargeCost pi_t = _pi[t];
    12381238                for (int ta = _next_out[t]; ta != last_out_t; ++ta) {
    1239                   if (_res_cap[ta] > 0 && 
     1239                  if (_res_cap[ta] > 0 &&
    12401240                      _cost[ta] + pi_t - _pi[_target[ta]] < 0)
    12411241                    ahead += _res_cap[ta];
     
    12881288            ++relabel_cnt;
    12891289          }
    1290        
     1290
    12911291          // Remove nodes that are not active nor hyper
    12921292        remove_nodes:
     
    12961296            _active_nodes.pop_front();
    12971297          }
    1298          
     1298
    12991299          // Global update heuristic
    13001300          if (relabel_cnt >= next_update_limit) {
Note: See TracChangeset for help on using the changeset viewer.