COIN-OR::LEMON - Graph Library

Changeset 1045:fe283caf6414 in lemon for lemon/cost_scaling.h


Ignore:
Timestamp:
03/15/11 17:59:57 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Minor improvements in CostScaling? (#417)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/cost_scaling.h

    r1042 r1045  
    576576    }
    577577
    578     /// \brief Reset all the parameters that have been given before.
    579     ///
    580     /// This function resets all the paramaters that have been given
    581     /// before using functions \ref lowerMap(), \ref upperMap(),
    582     /// \ref costMap(), \ref supplyMap(), \ref stSupply().
    583     ///
    584     /// It is useful for multiple run() calls. If this function is not
    585     /// used, all the parameters given before are kept for the next
    586     /// \ref run() call.
    587     /// However, the underlying digraph must not be modified after this
    588     /// class have been constructed, since it copies and extends the graph.
     578    /// \brief Reset the internal data structures and all the parameters
     579    /// that have been given before.
     580    ///
     581    /// This function resets the internal data structures and all the
     582    /// paramaters that have been given before using functions \ref lowerMap(),
     583    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
     584    ///
     585    /// It is useful for multiple \ref run() calls. By default, all the given
     586    /// parameters are kept for the next \ref run() call, unless
     587    /// \ref resetParams() or \ref reset() is used.
     588    /// If the underlying digraph was also modified after the construction
     589    /// of the class or the last \ref reset() call, then the \ref reset()
     590    /// function must be used, otherwise \ref resetParams() is sufficient.
     591    ///
     592    /// See \ref resetParams() for examples.
     593    ///
    589594    /// \return <tt>(*this)</tt>
     595    ///
     596    /// \see resetParams(), run()
    590597    CostScaling& reset() {
    591598      // Resize vectors
     
    891898      }
    892899
    893       return OPTIMAL;
    894     }
    895 
    896     // Execute the algorithm and transform the results
    897     void start(Method method) {
    898       // Maximum path length for partial augment
    899       const int MAX_PATH_LENGTH = 4;
    900 
    901900      // Initialize data structures for buckets
    902901      _max_rank = _alpha * _res_node_num;
     
    906905      _rank.resize(_res_node_num + 1);
    907906
    908       // Execute the algorithm
     907      return OPTIMAL;
     908    }
     909
     910    // Execute the algorithm and transform the results
     911    void start(Method method) {
     912      const int MAX_PARTIAL_PATH_LENGTH = 4;
     913
    909914      switch (method) {
    910915        case PUSH:
     
    915920          break;
    916921        case PARTIAL_AUGMENT:
    917           startAugment(MAX_PATH_LENGTH);
     922          startAugment(MAX_PARTIAL_PATH_LENGTH);
    918923          break;
    919924      }
     
    952957        LargeCost pi_u = _pi[u];
    953958        for (int a = _first_out[u]; a != last_out; ++a) {
    954           int v = _target[a];
    955           if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) {
    956             Value delta = _res_cap[a];
    957             _excess[u] -= delta;
    958             _excess[v] += delta;
    959             _res_cap[a] = 0;
    960             _res_cap[_reverse[a]] += delta;
     959          Value delta = _res_cap[a];
     960          if (delta > 0) {
     961            int v = _target[a];
     962            if (_cost[a] + pi_u - _pi[v] < 0) {
     963              _excess[u] -= delta;
     964              _excess[v] += delta;
     965              _res_cap[a] = 0;
     966              _res_cap[_reverse[a]] += delta;
     967            }
    961968          }
    962969        }
     
    10021009    // Global potential update heuristic
    10031010    void globalUpdate() {
    1004       int bucket_end = _root + 1;
     1011      const int bucket_end = _root + 1;
    10051012
    10061013      // Initialize buckets
     
    10091016      }
    10101017      Value total_excess = 0;
     1018      int b0 = bucket_end;
    10111019      for (int i = 0; i != _res_node_num; ++i) {
    10121020        if (_excess[i] < 0) {
    10131021          _rank[i] = 0;
    1014           _bucket_next[i] = _buckets[0];
    1015           _bucket_prev[_buckets[0]] = i;
    1016           _buckets[0] = i;
     1022          _bucket_next[i] = b0;
     1023          _bucket_prev[b0] = i;
     1024          b0 = i;
    10171025        } else {
    10181026          total_excess += _excess[i];
     
    10211029      }
    10221030      if (total_excess == 0) return;
     1031      _buckets[0] = b0;
    10231032
    10241033      // Search the buckets
     
    10421051                LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon;
    10431052                int new_rank_v = old_rank_v;
    1044                 if (nrc < LargeCost(_max_rank))
    1045                   new_rank_v = r + 1 + int(nrc);
     1053                if (nrc < LargeCost(_max_rank)) {
     1054                  new_rank_v = r + 1 + static_cast<int>(nrc);
     1055                }
    10461056
    10471057                // Change the rank of v
     
    10551065                      _buckets[old_rank_v] = _bucket_next[v];
    10561066                    } else {
    1057                       _bucket_next[_bucket_prev[v]] = _bucket_next[v];
    1058                       _bucket_prev[_bucket_next[v]] = _bucket_prev[v];
     1067                      int pv = _bucket_prev[v], nv = _bucket_next[v];
     1068                      _bucket_next[pv] = nv;
     1069                      _bucket_prev[nv] = pv;
    10591070                    }
    10601071                  }
    10611072
    1062                   // Insert v to its new bucket
    1063                   _bucket_next[v] = _buckets[new_rank_v];
    1064                   _bucket_prev[_buckets[new_rank_v]] = v;
     1073                  // Insert v into its new bucket
     1074                  int nv = _buckets[new_rank_v];
     1075                  _bucket_next[v] = nv;
     1076                  _bucket_prev[nv] = v;
    10651077                  _buckets[new_rank_v] = v;
    10661078                }
Note: See TracChangeset for help on using the changeset viewer.