# Changeset 1298:a78e5b779b69 in lemon for lemon/cycle_canceling.h

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

Files:
2 edited

### Legend:

Unmodified
 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;