Index: lemon/cost_scaling.h
===================================================================
--- lemon/cost_scaling.h (revision 1271)
+++ lemon/cost_scaling.h (revision 1296)
@@ -3,5 +3,5 @@
* This file is a part of LEMON, a generic C++ optimization library.
*
- * Copyright (C) 2003-2013
+ * Copyright (C) 2003-2010
* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
* (Egervary Research Group on Combinatorial Optimization, EGRES).
@@ -92,12 +92,9 @@
/// \ref CostScaling implements a cost scaling algorithm that performs
/// push/augment and relabel operations for finding a \ref min_cost_flow
- /// "minimum cost flow" \cite amo93networkflows,
- /// \cite goldberg90approximation,
- /// \cite goldberg97efficient, \cite bunnagel98efficient.
+ /// "minimum cost flow" \ref amo93networkflows, \ref goldberg90approximation,
+ /// \ref goldberg97efficient, \ref 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
@@ -154,6 +151,5 @@
typedef typename TR::LargeCost LargeCost;
- /// \brief The \ref lemon::CostScalingDefaultTraits "traits class"
- /// of the algorithm
+ /// The \ref CostScalingDefaultTraits "traits class" of the algorithm
typedef TR Traits;
@@ -215,6 +211,5 @@
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:
@@ -376,5 +371,4 @@
for (ArcIt a(_graph); a != INVALID; ++a) {
_lower[_arc_idf[a]] = map[a];
- _lower[_arc_idb[a]] = map[a];
}
return *this;
@@ -673,5 +667,5 @@
///
/// This function returns the total cost of the found flow.
- /// Its complexity is O(m).
+ /// Its complexity is O(e).
///
/// \note The return type of the function can be specified as a
@@ -907,10 +901,10 @@
return OPTIMAL;
}
-
- // 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;
@@ -995,5 +989,5 @@
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];
}
}
@@ -1288,5 +1282,5 @@
_buckets[r] = _bucket_next[u];
- // Search the incoming arcs of u
+ // Search the incomming arcs of u
LargeCost pi_u = _pi[u];
int last_out = _first_out[u+1];