# Changeset 1298:a78e5b779b69 in lemon

Ignore:
Timestamp:
10/17/13 15:08:41 (9 years ago)
Branch:
default
Children:
Parents:
1294:15e233f588da (diff), 1297:c0c2f5c87aa6 (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 bugfix #478

Location:
lemon
Files:
8 edited

Unmodified
Removed
• ## lemon/capacity_scaling.h

 r1270 // Parameters of the problem bool _have_lower; bool _has_lower; Value _sum_supply; template CapacityScaling& lowerMap(const LowerMap& map) { _have_lower = true; _has_lower = true; for (ArcIt a(_graph); a != INVALID; ++a) { _lower[_arc_idf[a]] = map[a]; _lower[_arc_idb[a]] = map[a]; } return *this; _cost[j] = _forward[j] ? 1 : -1; } _have_lower = false; _has_lower = false; return *this; } const Value MAX = std::numeric_limits::max(); int last_out; if (_have_lower) { if (_has_lower) { for (int i = 0; i != _root; ++i) { last_out = _first_out[i+1]; } // Check if the upper bound is greater or equal to the lower bound // on each arc. // Check if the upper bound is greater than or equal to the lower bound // on each forward arc. bool checkBoundMaps() { for (int j = 0; j != _res_arc_num; ++j) { if (_upper[j] < _lower[j]) return false; if (_forward[j] && _upper[j] < _lower[j]) return false; } return true; // Handle non-zero lower bounds if (_have_lower) { if (_has_lower) { int limit = _first_out[_root]; for (int j = 0; j != limit; ++j) { if (!_forward[j]) _res_cap[j] += _lower[j]; if (_forward[j]) _res_cap[_reverse[j]] += _lower[j]; } }
• ## lemon/capacity_scaling.h

 r1297 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2010 * Copyright (C) 2003-2013 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \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(m\log U (n+m)\log n)\f$, where U denotes the maximum /// of node supply and arc capacity values. /// /// This algorithm is typically slower than \ref CostScaling and typedef typename TR::Heap Heap; /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm /// \brief The \ref lemon::CapacityScalingDefaultTraits "traits class" /// of the algorithm typedef TR Traits; /// /// This function returns the total cost of the found flow. /// Its complexity is O(e). /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a return OPTIMAL; } // Check if the upper bound is greater than or equal to the lower bound // on each forward arc.
• ## lemon/cost_scaling.h

 r1271 // Parameters of the problem bool _have_lower; bool _has_lower; Value _sum_supply; int _sup_node_num; template CostScaling& lowerMap(const LowerMap& map) { _have_lower = true; _has_lower = true; for (ArcIt a(_graph); a != INVALID; ++a) { _lower[_arc_idf[a]] = map[a]; _lower[_arc_idb[a]] = map[a]; } return *this; _scost[_reverse[j]] = 0; } _have_lower = false; _has_lower = false; return *this; } const Value MAX = std::numeric_limits::max(); int last_out; if (_have_lower) { if (_has_lower) { for (int i = 0; i != _root; ++i) { last_out = _first_out[i+1]; sup[n] = _supply[_node_id[n]]; } if (_have_lower) { if (_has_lower) { for (ArcIt a(_graph); a != INVALID; ++a) { int j = _arc_idf[a]; } // Check if the upper bound is greater or equal to the lower bound // on each arc. // Check if the upper bound is greater than or equal to the lower bound // on each forward arc. bool checkBoundMaps() { for (int j = 0; j != _res_arc_num; ++j) { if (_upper[j] < _lower[j]) return false; if (_forward[j] && _upper[j] < _lower[j]) return false; } return true; // Handle non-zero lower bounds if (_have_lower) { if (_has_lower) { int limit = _first_out[_root]; for (int j = 0; j != limit; ++j) { if (!_forward[j]) _res_cap[j] += _lower[j]; if (_forward[j]) _res_cap[_reverse[j]] += _lower[j]; } }
• ## lemon/cost_scaling.h

 r1297 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2010 * Copyright (C) 2003-2013 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \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^2m\log(nK))\f$, where K denotes the maximum arc cost. /// /// In general, \ref NetworkSimplex and \ref CostScaling are the fastest typedef typename TR::LargeCost LargeCost; /// The \ref CostScalingDefaultTraits "traits class" of the algorithm /// \brief The \ref lemon::CostScalingDefaultTraits "traits class" /// of the algorithm typedef TR Traits; typedef std::vector LargeCostVector; typedef std::vector BoolVector; // Note: vector is used instead of vector for efficiency reasons // Note: vector is used instead of vector // for efficiency reasons private: /// /// This function returns the total cost of the found flow. /// Its complexity is O(e). /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a return OPTIMAL; } // Check if the upper bound is greater than or equal to the lower bound // on each forward arc. _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

 r1270 // Parameters of the problem bool _have_lower; bool _has_lower; Value _sum_supply; template CycleCanceling& lowerMap(const LowerMap& map) { _have_lower = true; _has_lower = true; for (ArcIt a(_graph); a != INVALID; ++a) { _lower[_arc_idf[a]] = map[a]; _lower[_arc_idb[a]] = map[a]; } return *this; _cost[_reverse[j]] = 0; } _have_lower = false; _has_lower = false; return *this; } const Value MAX = std::numeric_limits::max(); int last_out; if (_have_lower) { if (_has_lower) { for (int i = 0; i != _root; ++i) { last_out = _first_out[i+1]; sup[n] = _supply[_node_id[n]]; } if (_have_lower) { if (_has_lower) { for (ArcIt a(_graph); a != INVALID; ++a) { int j = _arc_idf[a]; } // Check if the upper bound is greater or equal to the lower bound // on each arc. // Check if the upper bound is greater than or equal to the lower bound // on each forward arc. bool checkBoundMaps() { for (int j = 0; j != _res_arc_num; ++j) { if (_upper[j] < _lower[j]) return false; if (_forward[j] && _upper[j] < _lower[j]) return false; } return true; // Handle non-zero lower bounds if (_have_lower) { if (_has_lower) { int limit = _first_out[_root]; for (int j = 0; j != limit; ++j) { if (!_forward[j]) _res_cap[j] += _lower[j]; if (_forward[j]) _res_cap[_reverse[j]] += _lower[j]; } }
• ## lemon/cycle_canceling.h

 r1297 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2010 * Copyright (C) 2003-2013 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \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 \f$O(n^2 m^2 \log n)\f$, /// 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)). /// Its running time complexity is \f$O(n^2 m^3 \log n)\f$. MINIMUM_MEAN_CYCLE_CANCELING, /// 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)). /// complexity is \f$O(n^2 m^2 \log n)\f$. CANCEL_AND_TIGHTEN }; /// /// This function returns the total cost of the found flow. /// Its complexity is O(e). /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a return OPTIMAL; } // Check if the upper bound is greater than or equal to the lower bound // on each forward arc. buildResidualNetwork(); while (true) { typename HwMmc::TerminationCause hw_tc = hw_mmc.findCycleMean(hw_iter_limit); hw_mmc.findCycle(); } // Compute delta value Value delta = INF;
• ## lemon/network_simplex.h

 r1270 // Parameters of the problem bool _have_lower; bool _has_lower; SupplyType _stype; Value _sum_supply; template NetworkSimplex& lowerMap(const LowerMap& map) { _have_lower = true; _has_lower = true; for (ArcIt a(_graph); a != INVALID; ++a) { _lower[_arc_id[a]] = map[a]; _cost[i] = 1; } _have_lower = false; _has_lower = false; _stype = GEQ; return *this; // Remove non-zero lower bounds if (_have_lower) { if (_has_lower) { for (int i = 0; i != _arc_num; ++i) { Value c = _lower[i]; } // Check if the upper bound is greater or equal to the lower bound // Check if the upper bound is greater than or equal to the lower bound // on each arc. bool checkBoundMaps() { // Transform the solution and the supply map to the original form if (_have_lower) { if (_has_lower) { for (int i = 0; i != _arc_num; ++i) { Value c = _lower[i];
• ## lemon/network_simplex.h

 r1297 * This file is a part of LEMON, a generic C++ optimization library. * * Copyright (C) 2003-2010 * Copyright (C) 2003-2013 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport * (Egervary Research Group on Combinatorial Optimization, EGRES). /// \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 /// /// This function returns the total cost of the found flow. /// Its complexity is O(e). /// Its complexity is O(m). /// /// \note The return type of the function can be specified as a return true; } // Check if the upper bound is greater than or equal to the lower bound // on each arc. } } 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.