COIN-OR::LEMON - Graph Library

Changeset 1071:879fcb781086 in lemon-main for lemon/cost_scaling.h


Ignore:
Timestamp:
07/30/13 15:24:45 (7 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Parents:
1069:d1a48668ddb4 (diff), 1070: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/cost_scaling.h

    r1053 r1071  
    764764      if (_sum_supply > 0) return INFEASIBLE;
    765765
     766      // Check lower and upper bounds
     767      LEMON_DEBUG(checkBoundMaps(),
     768          "Upper bounds must be greater or equal to the lower bounds");
     769
    766770
    767771      // Initialize vectors
     
    899903
    900904      return OPTIMAL;
     905    }
     906   
     907    // Check if the upper bound is greater or equal to the lower bound
     908    // on each arc.
     909    bool checkBoundMaps() {
     910      for (int j = 0; j != _res_arc_num; ++j) {
     911        if (_upper[j] < _lower[j]) return false;
     912      }
     913      return true;
    901914    }
    902915
  • lemon/cost_scaling.h

    r1070 r1071  
    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, \cite goldberg90approximation,
     95  /// \cite goldberg97efficient, \cite bunnagel98efficient.
    9696  /// It is a highly efficient primal-dual solution method, which
    9797  /// can be viewed as the generalization of the \ref Preflow
    9898  /// "preflow push-relabel" algorithm for the maximum flow problem.
     99  /// It is a polynomial algorithm, its running time complexity is
     100  /// \f$O(n^2e\log(nK))\f$, where <i>K</i> denotes the maximum arc cost.
    99101  ///
    100102  /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest
     
    12831285          _buckets[r] = _bucket_next[u];
    12841286
    1285           // Search the incomming arcs of u
     1287          // Search the incoming arcs of u
    12861288          LargeCost pi_u = _pi[u];
    12871289          int last_out = _first_out[u+1];
Note: See TracChangeset for help on using the changeset viewer.