COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
07/30/13 15:24:45 (7 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1239:d1a48668ddb4 (diff), 1240:ee9bac10f58e (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 #454

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/cycle_canceling.h

    r1221 r1241  
    671671      if (_sum_supply > 0) return INFEASIBLE;
    672672
     673      // Check lower and upper bounds
     674      LEMON_DEBUG(checkBoundMaps(),
     675          "Upper bounds must be greater or equal to the lower bounds");
     676
    673677
    674678      // Initialize vectors
     
    779783
    780784      return OPTIMAL;
     785    }
     786   
     787    // Check if the upper bound is greater or equal to the lower bound
     788    // on each arc.
     789    bool checkBoundMaps() {
     790      for (int j = 0; j != _res_arc_num; ++j) {
     791        if (_upper[j] < _lower[j]) return false;
     792      }
     793      return true;
    781794    }
    782795
  • lemon/cycle_canceling.h

    r1240 r1241  
    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 O(n<sup>2</sup>e<sup>2</sup>log(n)),
     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.
    136136      /// Its running time complexity is O(n<sup>2</sup>e<sup>3</sup>log(n)).
     
    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
    142142      /// complexity is O(n<sup>2</sup>e<sup>2</sup>log(n)).
Note: See TracChangeset for help on using the changeset viewer.