COIN-OR::LEMON - Graph Library

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/capacity_scaling.h

    r1270 r1298  
    164164
    165165    // Parameters of the problem
    166     bool _have_lower;
     166    bool _has_lower;
    167167    Value _sum_supply;
    168168
     
    357357    template <typename LowerMap>
    358358    CapacityScaling& lowerMap(const LowerMap& map) {
    359       _have_lower = true;
     359      _has_lower = true;
    360360      for (ArcIt a(_graph); a != INVALID; ++a) {
    361361        _lower[_arc_idf[a]] = map[a];
    362         _lower[_arc_idb[a]] = map[a];
    363362      }
    364363      return *this;
     
    544543        _cost[j] = _forward[j] ? 1 : -1;
    545544      }
    546       _have_lower = false;
     545      _has_lower = false;
    547546      return *this;
    548547    }
     
    755754      const Value MAX = std::numeric_limits<Value>::max();
    756755      int last_out;
    757       if (_have_lower) {
     756      if (_has_lower) {
    758757        for (int i = 0; i != _root; ++i) {
    759758          last_out = _first_out[i+1];
     
    840839    }
    841840
    842     // Check if the upper bound is greater or equal to the lower bound
    843     // on each arc.
     841    // Check if the upper bound is greater than or equal to the lower bound
     842    // on each forward arc.
    844843    bool checkBoundMaps() {
    845844      for (int j = 0; j != _res_arc_num; ++j) {
    846         if (_upper[j] < _lower[j]) return false;
     845        if (_forward[j] && _upper[j] < _lower[j]) return false;
    847846      }
    848847      return true;
     
    858857
    859858      // Handle non-zero lower bounds
    860       if (_have_lower) {
     859      if (_has_lower) {
    861860        int limit = _first_out[_root];
    862861        for (int j = 0; j != limit; ++j) {
    863           if (!_forward[j]) _res_cap[j] += _lower[j];
     862          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    864863        }
    865864      }
  • lemon/capacity_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).
     
    6767  /// \ref CapacityScaling implements the capacity scaling version
    6868  /// of the successive shortest path algorithm for finding a
    69   /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
    70   /// \ref edmondskarp72theoretical. It is an efficient dual
    71   /// solution method.
     69  /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows,
     70  /// \cite edmondskarp72theoretical. It is an efficient dual
     71  /// solution method, which runs in polynomial time
     72  /// \f$O(m\log U (n+m)\log n)\f$, where <i>U</i> denotes the maximum
     73  /// of node supply and arc capacity values.
    7274  ///
    7375  /// This algorithm is typically slower than \ref CostScaling and
     
    117119    typedef typename TR::Heap Heap;
    118120
    119     /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
     121    /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class"
     122    /// of the algorithm
    120123    typedef TR Traits;
    121124
     
    643646    ///
    644647    /// This function returns the total cost of the found flow.
    645     /// Its complexity is O(e).
     648    /// Its complexity is O(m).
    646649    ///
    647650    /// \note The return type of the function can be specified as a
     
    835838      return OPTIMAL;
    836839    }
    837    
     840
    838841    // Check if the upper bound is greater than or equal to the lower bound
    839842    // on each forward arc.
Note: See TracChangeset for help on using the changeset viewer.