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

    r1270 r1298  
    196196
    197197    // Parameters of the problem
    198     bool _have_lower;
     198    bool _has_lower;
    199199    Value _sum_supply;
    200200
     
    279279    template <typename LowerMap>
    280280    CycleCanceling& lowerMap(const LowerMap& map) {
    281       _have_lower = true;
     281      _has_lower = true;
    282282      for (ArcIt a(_graph); a != INVALID; ++a) {
    283283        _lower[_arc_idf[a]] = map[a];
    284         _lower[_arc_idb[a]] = map[a];
    285284      }
    286285      return *this;
     
    472471        _cost[_reverse[j]] = 0;
    473472      }
    474       _have_lower = false;
     473      _has_lower = false;
    475474      return *this;
    476475    }
     
    685684      const Value MAX = std::numeric_limits<Value>::max();
    686685      int last_out;
    687       if (_have_lower) {
     686      if (_has_lower) {
    688687        for (int i = 0; i != _root; ++i) {
    689688          last_out = _first_out[i+1];
     
    728727        sup[n] = _supply[_node_id[n]];
    729728      }
    730       if (_have_lower) {
     729      if (_has_lower) {
    731730        for (ArcIt a(_graph); a != INVALID; ++a) {
    732731          int j = _arc_idf[a];
     
    785784    }
    786785
    787     // Check if the upper bound is greater or equal to the lower bound
    788     // on each arc.
     786    // Check if the upper bound is greater than or equal to the lower bound
     787    // on each forward arc.
    789788    bool checkBoundMaps() {
    790789      for (int j = 0; j != _res_arc_num; ++j) {
    791         if (_upper[j] < _lower[j]) return false;
     790        if (_forward[j] && _upper[j] < _lower[j]) return false;
    792791      }
    793792      return true;
     
    836835
    837836      // Handle non-zero lower bounds
    838       if (_have_lower) {
     837      if (_has_lower) {
    839838        int limit = _first_out[_root];
    840839        for (int j = 0; j != limit; ++j) {
    841           if (!_forward[j]) _res_cap[j] += _lower[j];
     840          if (_forward[j]) _res_cap[_reverse[j]] += _lower[j];
    842841        }
    843842      }
  • lemon/cycle_canceling.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).
     
    4848  /// \ref CycleCanceling implements three different cycle-canceling
    4949  /// algorithms for finding a \ref min_cost_flow "minimum cost flow"
    50   /// \ref amo93networkflows, \ref klein67primal,
    51   /// \ref goldberg89cyclecanceling.
     50  /// \cite amo93networkflows, \cite klein67primal,
     51  /// \cite goldberg89cyclecanceling.
    5252  /// The most efficent one is the \ref CANCEL_AND_TIGHTEN
    5353  /// "Cancel-and-Tighten" algorithm, thus it is the default method.
    54   /// It runs in strongly polynomial time, but in practice, it is typically
    55   /// orders of magnitude slower than the scaling algorithms and
    56   /// \ref NetworkSimplex.
     54  /// It runs in strongly polynomial time \f$O(n^2 m^2 \log n)\f$,
     55  /// but in practice, it is typically orders of magnitude slower than
     56  /// the scaling algorithms and \ref NetworkSimplex.
    5757  /// (For more information, see \ref min_cost_flow_algs "the module page".)
    5858  ///
     
    132132      /// The "Minimum Mean Cycle-Canceling" algorithm, which is a
    133133      /// well-known strongly polynomial method
    134       /// \ref goldberg89cyclecanceling. It improves along a
     134      /// \cite goldberg89cyclecanceling. It improves along a
    135135      /// \ref min_mean_cycle "minimum mean cycle" in each iteration.
    136       /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
     136      /// Its running time complexity is \f$O(n^2 m^3 \log n)\f$.
    137137      MINIMUM_MEAN_CYCLE_CANCELING,
    138138      /// The "Cancel-and-Tighten" algorithm, which can be viewed as an
    139139      /// improved version of the previous method
    140       /// \ref goldberg89cyclecanceling.
     140      /// \cite goldberg89cyclecanceling.
    141141      /// It is faster both in theory and in practice, its running time
    142       /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
     142      /// complexity is \f$O(n^2 m^2 \log n)\f$.
    143143      CANCEL_AND_TIGHTEN
    144144    };
     
    576576    ///
    577577    /// This function returns the total cost of the found flow.
    578     /// Its complexity is O(e).
     578    /// Its complexity is O(m).
    579579    ///
    580580    /// \note The return type of the function can be specified as a
     
    783783      return OPTIMAL;
    784784    }
    785    
     785
    786786    // Check if the upper bound is greater than or equal to the lower bound
    787787    // on each forward arc.
     
    960960      buildResidualNetwork();
    961961      while (true) {
    962        
     962
    963963        typename HwMmc::TerminationCause hw_tc =
    964964            hw_mmc.findCycleMean(hw_iter_limit);
     
    976976          hw_mmc.findCycle();
    977977        }
    978        
     978
    979979        // Compute delta value
    980980        Value delta = INF;
Note: See TracChangeset for help on using the changeset viewer.