COIN-OR::LEMON - Graph Library

Changeset 1298:a78e5b779b69 in lemon for lemon/cost_scaling.h


Ignore:
Timestamp:
10/17/13 15:08:41 (6 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Children:
1299:b6bad215bccd, 1300:62dba6c90f35
Parents:
1294:15e233f588da (diff), 1297:c0c2f5c87aa6 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Phase:
public
Message:

Merge bugfix #478

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/cost_scaling.h

    r1271 r1298  
    257257
    258258    // Parameters of the problem
    259     bool _have_lower;
     259    bool _has_lower;
    260260    Value _sum_supply;
    261261    int _sup_node_num;
     
    373373    template <typename LowerMap>
    374374    CostScaling& lowerMap(const LowerMap& map) {
    375       _have_lower = true;
     375      _has_lower = true;
    376376      for (ArcIt a(_graph); a != INVALID; ++a) {
    377377        _lower[_arc_idf[a]] = map[a];
    378         _lower[_arc_idb[a]] = map[a];
    379378      }
    380379      return *this;
     
    569568        _scost[_reverse[j]] = 0;
    570569      }
    571       _have_lower = false;
     570      _has_lower = false;
    572571      return *this;
    573572    }
     
    781780      const Value MAX = std::numeric_limits<Value>::max();
    782781      int last_out;
    783       if (_have_lower) {
     782      if (_has_lower) {
    784783        for (int i = 0; i != _root; ++i) {
    785784          last_out = _first_out[i+1];
     
    838837        sup[n] = _supply[_node_id[n]];
    839838      }
    840       if (_have_lower) {
     839      if (_has_lower) {
    841840        for (ArcIt a(_graph); a != INVALID; ++a) {
    842841          int j = _arc_idf[a];
     
    908907    }
    909908
    910     // Check if the upper bound is greater or equal to the lower bound
    911     // on each arc.
     909    // Check if the upper bound is greater than or equal to the lower bound
     910    // on each forward arc.
    912911    bool checkBoundMaps() {
    913912      for (int j = 0; j != _res_arc_num; ++j) {
    914         if (_upper[j] < _lower[j]) return false;
     913        if (_forward[j] && _upper[j] < _lower[j]) return false;
    915914      }
    916915      return true;
     
    992991
    993992      // Handle non-zero lower bounds
    994       if (_have_lower) {
     993      if (_has_lower) {
    995994        int limit = _first_out[_root];
    996995        for (int j = 0; j != limit; ++j) {
    997           if (!_forward[j]) _res_cap[j] += _lower[j];
     996          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    998997        }
    999998      }
  • lemon/cost_scaling.h

    r1297 r1298  
    33 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    5  * Copyright (C) 2003-2010
     5 * Copyright (C) 2003-2013
    66 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
    77 * (Egervary Research Group on Combinatorial Optimization, EGRES).
     
    9292  /// \ref CostScaling implements a cost scaling algorithm that performs
    9393  /// push/augment and relabel operations for finding a \ref min_cost_flow
    94   /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
    95   /// \ref goldberg97efficient, \ref bunnagel98efficient.
     94  /// "minimum cost flow" \cite amo93networkflows,
     95  /// \cite goldberg90approximation,
     96  /// \cite goldberg97efficient, \cite bunnagel98efficient.
    9697  /// It is a highly efficient primal-dual solution method, which
    9798  /// can be viewed as the generalization of the \ref Preflow
    9899  /// "preflow push-relabel" algorithm for the maximum flow problem.
     100  /// It is a polynomial algorithm, its running time complexity is
     101  /// \f$O(n^2m\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
    99102  ///
    100103  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     
    151154    typedef typename TR::LargeCost LargeCost;
    152155
    153     /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
     156    /// \brief The \ref lemon::CostScalingDefaultTraits "traits class"
     157    /// of the algorithm
    154158    typedef TR Traits;
    155159
     
    211215    typedef std::vector<LargeCost> LargeCostVector;
    212216    typedef std::vector<char> BoolVector;
    213     // Note: vector<char> is used instead of vector<bool> for efficiency reasons
     217    // Note: vector<char> is used instead of vector<bool>
     218    // for efficiency reasons
    214219
    215220  private:
     
    667672    ///
    668673    /// This function returns the total cost of the found flow.
    669     /// Its complexity is O(e).
     674    /// Its complexity is O(m).
    670675    ///
    671676    /// \note The return type of the function can be specified as a
     
    901906      return OPTIMAL;
    902907    }
    903    
     908
    904909    // Check if the upper bound is greater than or equal to the lower bound
    905910    // on each forward arc.
     
    12821287          _buckets[r] = _bucket_next[u];
    12831288
    1284           // Search the incomming arcs of u
     1289          // Search the incoming arcs of u
    12851290          LargeCost pi_u = _pi[u];
    12861291          int last_out = _first_out[u+1];
Note: See TracChangeset for help on using the changeset viewer.