# Changeset 1298:a78e5b779b69 in lemon for lemon/cost_scaling.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 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];