COIN-OR::LEMON - Graph Library

Changeset 1241:879fcb781086 in lemon


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

Location:
lemon
Files:
8 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
  • lemon/cost_scaling.h

    r1221 r1241  
    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

    r1240 r1241  
    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];
  • 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)).
  • lemon/network_simplex.h

    r1221 r1241  
    10681068             (_stype == LEQ && _sum_supply >= 0)) ) return false;
    10691069
     1070      // Check lower and upper bounds
     1071      LEMON_DEBUG(checkBoundMaps(),
     1072          "Upper bounds must be greater or equal to the lower bounds");
     1073
    10701074      // Remove non-zero lower bounds
    10711075      if (_have_lower) {
     
    12311235      return true;
    12321236    }
     1237   
     1238    // Check if the upper bound is greater or equal to the lower bound
     1239    // on each arc.
     1240    bool checkBoundMaps() {
     1241      for (int j = 0; j != _arc_num; ++j) {
     1242        if (_upper[j] < _lower[j]) return false;
     1243      }
     1244      return true;
     1245    }
    12331246
    12341247    // Find the join node
  • lemon/network_simplex.h

    r1240 r1241  
    4242  /// \ref NetworkSimplex implements the primal Network Simplex algorithm
    4343  /// for finding a \ref min_cost_flow "minimum cost flow"
    44   /// \ref amo93networkflows, \ref dantzig63linearprog,
    45   /// \ref kellyoneill91netsimplex.
     44  /// \cite amo93networkflows, \cite dantzig63linearprog,
     45  /// \cite kellyoneill91netsimplex.
    4646  /// This algorithm is a highly efficient specialized version of the
    4747  /// linear programming simplex method directly for the minimum cost
     
    15171517          }
    15181518        } else {
    1519           // Find the min. cost incomming arc for each demand node
     1519          // Find the min. cost incoming arc for each demand node
    15201520          for (int i = 0; i != int(demand_nodes.size()); ++i) {
    15211521            Node v = demand_nodes[i];
Note: See TracChangeset for help on using the changeset viewer.