COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
07/30/13 15:24:45 (6 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/capacity_scaling.h

    r1221 r1241  
    740740      if (_sum_supply > 0) return INFEASIBLE;
    741741
     742      // Check lower and upper bounds
     743      LEMON_DEBUG(checkBoundMaps(),
     744          "Upper bounds must be greater or equal to the lower bounds");
     745
     746
    742747      // Initialize vectors
    743748      for (int i = 0; i != _root; ++i) {
     
    832837
    833838      return OPTIMAL;
     839    }
     840   
     841    // Check if the upper bound is greater or equal to the lower bound
     842    // on each arc.
     843    bool checkBoundMaps() {
     844      for (int j = 0; j != _res_arc_num; ++j) {
     845        if (_upper[j] < _lower[j]) return false;
     846      }
     847      return true;
    834848    }
    835849
  • lemon/capacity_scaling.h

    r1240 r1241  
    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(e\log U (n+e)\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
Note: See TracChangeset for help on using the changeset viewer.