# Changeset 1241:879fcb781086 in lemon

Ignore:
Timestamp:
07/30/13 15:24:45 (7 years ago)
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

Unmodified
Removed
• ## lemon/capacity_scaling.h

 r1221 if (_sum_supply > 0) return INFEASIBLE; // Check lower and upper bounds LEMON_DEBUG(checkBoundMaps(), "Upper bounds must be greater or equal to the lower bounds"); // Initialize vectors for (int i = 0; i != _root; ++i) { return OPTIMAL; } // Check if the upper bound is greater or equal to the lower bound // on each arc. bool checkBoundMaps() { for (int j = 0; j != _res_arc_num; ++j) { if (_upper[j] < _lower[j]) return false; } return true; }
• ## lemon/capacity_scaling.h

 r1240 /// \ref CapacityScaling implements the capacity scaling version /// of the successive shortest path algorithm for finding a /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows, /// \ref edmondskarp72theoretical. It is an efficient dual /// solution method. /// \ref min_cost_flow "minimum cost flow" \cite amo93networkflows, /// \cite edmondskarp72theoretical. It is an efficient dual /// solution method, which runs in polynomial time /// \f$O(e\log U (n+e)\log n)\f$, where U denotes the maximum /// of node supply and arc capacity values. /// /// This algorithm is typically slower than \ref CostScaling and
• ## lemon/cost_scaling.h

 r1221 if (_sum_supply > 0) return INFEASIBLE; // Check lower and upper bounds LEMON_DEBUG(checkBoundMaps(), "Upper bounds must be greater or equal to the lower bounds"); // Initialize vectors return OPTIMAL; } // Check if the upper bound is greater or equal to the lower bound // on each arc. bool checkBoundMaps() { for (int j = 0; j != _res_arc_num; ++j) { if (_upper[j] < _lower[j]) return false; } return true; }
• ## lemon/cost_scaling.h

 r1240 /// \ref CostScaling implements a cost scaling algorithm that performs /// push/augment and relabel operations for finding a \ref min_cost_flow /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation, /// \ref goldberg97efficient, \ref bunnagel98efficient. /// "minimum cost flow" \cite amo93networkflows, \cite goldberg90approximation, /// \cite goldberg97efficient, \cite bunnagel98efficient. /// It is a highly efficient primal-dual solution method, which /// can be viewed as the generalization of the \ref Preflow /// "preflow push-relabel" algorithm for the maximum flow problem. /// It is a polynomial algorithm, its running time complexity is /// \f$O(n^2e\log(nK))\f$, where K denotes the maximum arc cost. /// /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest _buckets[r] = _bucket_next[u]; // Search the incomming arcs of u // Search the incoming arcs of u LargeCost pi_u = _pi[u]; int last_out = _first_out[u+1];
• ## lemon/cycle_canceling.h

 r1221 if (_sum_supply > 0) return INFEASIBLE; // Check lower and upper bounds LEMON_DEBUG(checkBoundMaps(), "Upper bounds must be greater or equal to the lower bounds"); // Initialize vectors return OPTIMAL; } // Check if the upper bound is greater or equal to the lower bound // on each arc. bool checkBoundMaps() { for (int j = 0; j != _res_arc_num; ++j) { if (_upper[j] < _lower[j]) return false; } return true; }
• ## lemon/cycle_canceling.h

 r1240 /// \ref CycleCanceling implements three different cycle-canceling /// algorithms for finding a \ref min_cost_flow "minimum cost flow" /// \ref amo93networkflows, \ref klein67primal, /// \ref goldberg89cyclecanceling. /// \cite amo93networkflows, \cite klein67primal, /// \cite goldberg89cyclecanceling. /// The most efficent one is the \ref CANCEL_AND_TIGHTEN /// "Cancel-and-Tighten" algorithm, thus it is the default method. /// It runs in strongly polynomial time, but in practice, it is typically /// orders of magnitude slower than the scaling algorithms and /// \ref NetworkSimplex. /// It runs in strongly polynomial time O(n2e2log(n)), /// but in practice, it is typically orders of magnitude slower than /// the scaling algorithms and \ref NetworkSimplex. /// (For more information, see \ref min_cost_flow_algs "the module page".) /// /// The "Minimum Mean Cycle-Canceling" algorithm, which is a /// well-known strongly polynomial method /// \ref goldberg89cyclecanceling. It improves along a /// \cite goldberg89cyclecanceling. It improves along a /// \ref min_mean_cycle "minimum mean cycle" in each iteration. /// Its running time complexity is O(n2e3log(n)). /// The "Cancel-and-Tighten" algorithm, which can be viewed as an /// improved version of the previous method /// \ref goldberg89cyclecanceling. /// \cite goldberg89cyclecanceling. /// It is faster both in theory and in practice, its running time /// complexity is O(n2e2log(n)).
• ## lemon/network_simplex.h

 r1221 (_stype == LEQ && _sum_supply >= 0)) ) return false; // Check lower and upper bounds LEMON_DEBUG(checkBoundMaps(), "Upper bounds must be greater or equal to the lower bounds"); // Remove non-zero lower bounds if (_have_lower) { return true; } // Check if the upper bound is greater or equal to the lower bound // on each arc. bool checkBoundMaps() { for (int j = 0; j != _arc_num; ++j) { if (_upper[j] < _lower[j]) return false; } return true; } // Find the join node
• ## lemon/network_simplex.h

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