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

Ignore:
Timestamp:
10/17/13 15:08:41 (6 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 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.