Add a cost scaling min cost flow algorithm.
Add a cost scaling algorithm, which is performing generalized
push-relabel operations. It is almost as efficient as the capacity
scaling algorithm, but slower than network simplex.
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/cost_scaling.h Mon Feb 18 03:34:16 2008 +0000
1.3 @@ -0,0 +1,561 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2008
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_COST_SCALING_H
1.23 +#define LEMON_COST_SCALING_H
1.24 +
1.25 +/// \ingroup min_cost_flow
1.26 +///
1.27 +/// \file
1.28 +/// \brief Cost scaling algorithm for finding a minimum cost flow.
1.29 +
1.30 +#include <deque>
1.31 +#include <lemon/graph_adaptor.h>
1.32 +#include <lemon/graph_utils.h>
1.33 +#include <lemon/maps.h>
1.34 +#include <lemon/math.h>
1.35 +
1.36 +#include <lemon/circulation.h>
1.37 +#include <lemon/bellman_ford.h>
1.38 +
1.39 +namespace lemon {
1.40 +
1.41 + /// \addtogroup min_cost_flow
1.42 + /// @{
1.43 +
1.44 + /// \brief Implementation of the cost scaling algorithm for finding a
1.45 + /// minimum cost flow.
1.46 + ///
1.47 + /// \ref CostScaling implements the cost scaling algorithm performing
1.48 + /// generalized push-relabel operations for finding a minimum cost
1.49 + /// flow.
1.50 + ///
1.51 + /// \tparam Graph The directed graph type the algorithm runs on.
1.52 + /// \tparam LowerMap The type of the lower bound map.
1.53 + /// \tparam CapacityMap The type of the capacity (upper bound) map.
1.54 + /// \tparam CostMap The type of the cost (length) map.
1.55 + /// \tparam SupplyMap The type of the supply map.
1.56 + ///
1.57 + /// \warning
1.58 + /// - Edge capacities and costs should be \e non-negative \e integers.
1.59 + /// - Supply values should be \e signed \e integers.
1.60 + /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
1.61 + /// - \c CapacityMap::Value and \c SupplyMap::Value must be
1.62 + /// convertible to each other.
1.63 + /// - All value types must be convertible to \c CostMap::Value, which
1.64 + /// must be signed type.
1.65 + ///
1.66 + /// \note Edge costs are multiplied with the number of nodes during
1.67 + /// the algorithm so overflow problems may arise more easily than with
1.68 + /// other minimum cost flow algorithms.
1.69 + /// If it is available, <tt>long long int</tt> type is used instead of
1.70 + /// <tt>long int</tt> in the inside computations.
1.71 + ///
1.72 + /// \author Peter Kovacs
1.73 +
1.74 + template < typename Graph,
1.75 + typename LowerMap = typename Graph::template EdgeMap<int>,
1.76 + typename CapacityMap = typename Graph::template EdgeMap<int>,
1.77 + typename CostMap = typename Graph::template EdgeMap<int>,
1.78 + typename SupplyMap = typename Graph::template NodeMap<int> >
1.79 + class CostScaling
1.80 + {
1.81 + GRAPH_TYPEDEFS(typename Graph);
1.82 +
1.83 + typedef typename CapacityMap::Value Capacity;
1.84 + typedef typename CostMap::Value Cost;
1.85 + typedef typename SupplyMap::Value Supply;
1.86 + typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
1.87 + typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
1.88 +
1.89 + typedef ResGraphAdaptor< const Graph, Capacity,
1.90 + CapacityEdgeMap, CapacityEdgeMap > ResGraph;
1.91 + typedef typename ResGraph::Edge ResEdge;
1.92 +
1.93 +#if defined __GNUC__ && !defined __STRICT_ANSI__
1.94 + typedef long long int LCost;
1.95 +#else
1.96 + typedef long int LCost;
1.97 +#endif
1.98 + typedef typename Graph::template EdgeMap<LCost> LargeCostMap;
1.99 +
1.100 + public:
1.101 +
1.102 + /// The type of the flow map.
1.103 + typedef CapacityEdgeMap FlowMap;
1.104 + /// The type of the potential map.
1.105 + typedef typename Graph::template NodeMap<LCost> PotentialMap;
1.106 +
1.107 + private:
1.108 +
1.109 + /// \brief Map adaptor class for handling residual edge costs.
1.110 + ///
1.111 + /// \ref ResidualCostMap is a map adaptor class for handling
1.112 + /// residual edge costs.
1.113 + class ResidualCostMap : public MapBase<ResEdge, LCost>
1.114 + {
1.115 + private:
1.116 +
1.117 + const LargeCostMap &_cost_map;
1.118 +
1.119 + public:
1.120 +
1.121 + ///\e
1.122 + ResidualCostMap(const LargeCostMap &cost_map) :
1.123 + _cost_map(cost_map) {}
1.124 +
1.125 + ///\e
1.126 + LCost operator[](const ResEdge &e) const {
1.127 + return ResGraph::forward(e) ? _cost_map[e] : -_cost_map[e];
1.128 + }
1.129 +
1.130 + }; //class ResidualCostMap
1.131 +
1.132 + /// \brief Map adaptor class for handling reduced edge costs.
1.133 + ///
1.134 + /// \ref ReducedCostMap is a map adaptor class for handling reduced
1.135 + /// edge costs.
1.136 + class ReducedCostMap : public MapBase<Edge, LCost>
1.137 + {
1.138 + private:
1.139 +
1.140 + const Graph &_gr;
1.141 + const LargeCostMap &_cost_map;
1.142 + const PotentialMap &_pot_map;
1.143 +
1.144 + public:
1.145 +
1.146 + ///\e
1.147 + ReducedCostMap( const Graph &gr,
1.148 + const LargeCostMap &cost_map,
1.149 + const PotentialMap &pot_map ) :
1.150 + _gr(gr), _cost_map(cost_map), _pot_map(pot_map) {}
1.151 +
1.152 + ///\e
1.153 + LCost operator[](const Edge &e) const {
1.154 + return _cost_map[e] + _pot_map[_gr.source(e)]
1.155 + - _pot_map[_gr.target(e)];
1.156 + }
1.157 +
1.158 + }; //class ReducedCostMap
1.159 +
1.160 + private:
1.161 +
1.162 + // Scaling factor
1.163 + static const int ALPHA = 4;
1.164 +
1.165 + // Paramters for heuristics
1.166 + static const int BF_HEURISTIC_EPSILON_BOUND = 5000;
1.167 + static const int BF_HEURISTIC_BOUND_FACTOR = 3;
1.168 +
1.169 + private:
1.170 +
1.171 + // The directed graph the algorithm runs on
1.172 + const Graph &_graph;
1.173 + // The original lower bound map
1.174 + const LowerMap *_lower;
1.175 + // The modified capacity map
1.176 + CapacityEdgeMap _capacity;
1.177 + // The original cost map
1.178 + const CostMap &_orig_cost;
1.179 + // The scaled cost map
1.180 + LargeCostMap _cost;
1.181 + // The modified supply map
1.182 + SupplyNodeMap _supply;
1.183 + bool _valid_supply;
1.184 +
1.185 + // Edge map of the current flow
1.186 + FlowMap _flow;
1.187 + // Node map of the current potentials
1.188 + PotentialMap _potential;
1.189 +
1.190 + // The residual graph
1.191 + ResGraph _res_graph;
1.192 + // The residual cost map
1.193 + ResidualCostMap _res_cost;
1.194 + // The reduced cost map
1.195 + ReducedCostMap _red_cost;
1.196 + // The excess map
1.197 + SupplyNodeMap _excess;
1.198 + // The epsilon parameter used for cost scaling
1.199 + LCost _epsilon;
1.200 +
1.201 + public:
1.202 +
1.203 + /// \brief General constructor of the class (with lower bounds).
1.204 + ///
1.205 + /// General constructor of the class (with lower bounds).
1.206 + ///
1.207 + /// \param graph The directed graph the algorithm runs on.
1.208 + /// \param lower The lower bounds of the edges.
1.209 + /// \param capacity The capacities (upper bounds) of the edges.
1.210 + /// \param cost The cost (length) values of the edges.
1.211 + /// \param supply The supply values of the nodes (signed).
1.212 + CostScaling( const Graph &graph,
1.213 + const LowerMap &lower,
1.214 + const CapacityMap &capacity,
1.215 + const CostMap &cost,
1.216 + const SupplyMap &supply ) :
1.217 + _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
1.218 + _cost(graph), _supply(graph), _flow(graph, 0), _potential(graph, 0),
1.219 + _res_graph(graph, _capacity, _flow), _res_cost(_cost),
1.220 + _red_cost(graph, _cost, _potential), _excess(graph, 0)
1.221 + {
1.222 + // Removing non-zero lower bounds
1.223 + _capacity = subMap(capacity, lower);
1.224 + Supply sum = 0;
1.225 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.226 + Supply s = supply[n];
1.227 + for (InEdgeIt e(_graph, n); e != INVALID; ++e)
1.228 + s += lower[e];
1.229 + for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
1.230 + s -= lower[e];
1.231 + _supply[n] = s;
1.232 + sum += s;
1.233 + }
1.234 + _valid_supply = sum == 0;
1.235 + }
1.236 +
1.237 + /// \brief General constructor of the class (without lower bounds).
1.238 + ///
1.239 + /// General constructor of the class (without lower bounds).
1.240 + ///
1.241 + /// \param graph The directed graph the algorithm runs on.
1.242 + /// \param capacity The capacities (upper bounds) of the edges.
1.243 + /// \param cost The cost (length) values of the edges.
1.244 + /// \param supply The supply values of the nodes (signed).
1.245 + CostScaling( const Graph &graph,
1.246 + const CapacityMap &capacity,
1.247 + const CostMap &cost,
1.248 + const SupplyMap &supply ) :
1.249 + _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost),
1.250 + _cost(graph), _supply(supply), _flow(graph, 0), _potential(graph, 0),
1.251 + _res_graph(graph, _capacity, _flow), _res_cost(_cost),
1.252 + _red_cost(graph, _cost, _potential), _excess(graph, 0)
1.253 + {
1.254 + // Checking the sum of supply values
1.255 + Supply sum = 0;
1.256 + for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
1.257 + _valid_supply = sum == 0;
1.258 + }
1.259 +
1.260 + /// \brief Simple constructor of the class (with lower bounds).
1.261 + ///
1.262 + /// Simple constructor of the class (with lower bounds).
1.263 + ///
1.264 + /// \param graph The directed graph the algorithm runs on.
1.265 + /// \param lower The lower bounds of the edges.
1.266 + /// \param capacity The capacities (upper bounds) of the edges.
1.267 + /// \param cost The cost (length) values of the edges.
1.268 + /// \param s The source node.
1.269 + /// \param t The target node.
1.270 + /// \param flow_value The required amount of flow from node \c s
1.271 + /// to node \c t (i.e. the supply of \c s and the demand of \c t).
1.272 + CostScaling( const Graph &graph,
1.273 + const LowerMap &lower,
1.274 + const CapacityMap &capacity,
1.275 + const CostMap &cost,
1.276 + Node s, Node t,
1.277 + Supply flow_value ) :
1.278 + _graph(graph), _lower(&lower), _capacity(graph), _orig_cost(cost),
1.279 + _cost(graph), _supply(graph), _flow(graph, 0), _potential(graph, 0),
1.280 + _res_graph(graph, _capacity, _flow), _res_cost(_cost),
1.281 + _red_cost(graph, _cost, _potential), _excess(graph, 0)
1.282 + {
1.283 + // Removing nonzero lower bounds
1.284 + _capacity = subMap(capacity, lower);
1.285 + for (NodeIt n(_graph); n != INVALID; ++n) {
1.286 + Supply sum = 0;
1.287 + if (n == s) sum = flow_value;
1.288 + if (n == t) sum = -flow_value;
1.289 + for (InEdgeIt e(_graph, n); e != INVALID; ++e)
1.290 + sum += lower[e];
1.291 + for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
1.292 + sum -= lower[e];
1.293 + _supply[n] = sum;
1.294 + }
1.295 + _valid_supply = true;
1.296 + }
1.297 +
1.298 + /// \brief Simple constructor of the class (without lower bounds).
1.299 + ///
1.300 + /// Simple constructor of the class (without lower bounds).
1.301 + ///
1.302 + /// \param graph The directed graph the algorithm runs on.
1.303 + /// \param capacity The capacities (upper bounds) of the edges.
1.304 + /// \param cost The cost (length) values of the edges.
1.305 + /// \param s The source node.
1.306 + /// \param t The target node.
1.307 + /// \param flow_value The required amount of flow from node \c s
1.308 + /// to node \c t (i.e. the supply of \c s and the demand of \c t).
1.309 + CostScaling( const Graph &graph,
1.310 + const CapacityMap &capacity,
1.311 + const CostMap &cost,
1.312 + Node s, Node t,
1.313 + Supply flow_value ) :
1.314 + _graph(graph), _lower(NULL), _capacity(capacity), _orig_cost(cost),
1.315 + _cost(graph), _supply(graph, 0), _flow(graph, 0), _potential(graph, 0),
1.316 + _res_graph(graph, _capacity, _flow), _res_cost(_cost),
1.317 + _red_cost(graph, _cost, _potential), _excess(graph, 0)
1.318 + {
1.319 + _supply[s] = flow_value;
1.320 + _supply[t] = -flow_value;
1.321 + _valid_supply = true;
1.322 + }
1.323 +
1.324 + /// \brief Runs the algorithm.
1.325 + ///
1.326 + /// Runs the algorithm.
1.327 + ///
1.328 + /// \return \c true if a feasible flow can be found.
1.329 + bool run() {
1.330 + init() && start();
1.331 + }
1.332 +
1.333 + /// \brief Returns a const reference to the edge map storing the
1.334 + /// found flow.
1.335 + ///
1.336 + /// Returns a const reference to the edge map storing the found flow.
1.337 + ///
1.338 + /// \pre \ref run() must be called before using this function.
1.339 + const FlowMap& flowMap() const {
1.340 + return _flow;
1.341 + }
1.342 +
1.343 + /// \brief Returns a const reference to the node map storing the
1.344 + /// found potentials (the dual solution).
1.345 + ///
1.346 + /// Returns a const reference to the node map storing the found
1.347 + /// potentials (the dual solution).
1.348 + ///
1.349 + /// \pre \ref run() must be called before using this function.
1.350 + const PotentialMap& potentialMap() const {
1.351 + return _potential;
1.352 + }
1.353 +
1.354 + /// \brief Returns the total cost of the found flow.
1.355 + ///
1.356 + /// Returns the total cost of the found flow. The complexity of the
1.357 + /// function is \f$ O(e) \f$.
1.358 + ///
1.359 + /// \pre \ref run() must be called before using this function.
1.360 + Cost totalCost() const {
1.361 + Cost c = 0;
1.362 + for (EdgeIt e(_graph); e != INVALID; ++e)
1.363 + c += _flow[e] * _orig_cost[e];
1.364 + return c;
1.365 + }
1.366 +
1.367 + private:
1.368 +
1.369 + /// Initializes the algorithm.
1.370 + bool init() {
1.371 + if (!_valid_supply) return false;
1.372 +
1.373 + // Initializing the scaled cost map and the epsilon parameter
1.374 + Cost max_cost = 0;
1.375 + int node_num = countNodes(_graph);
1.376 + for (EdgeIt e(_graph); e != INVALID; ++e) {
1.377 + _cost[e] = LCost(_orig_cost[e]) * node_num * ALPHA;
1.378 + if (_orig_cost[e] > max_cost) max_cost = _orig_cost[e];
1.379 + }
1.380 + _epsilon = max_cost * node_num;
1.381 +
1.382 + // Finding a feasible flow using Circulation
1.383 + Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
1.384 + SupplyMap >
1.385 + circulation( _graph, constMap<Edge>((Capacity)0), _capacity,
1.386 + _supply );
1.387 + return circulation.flowMap(_flow).run();
1.388 + }
1.389 +
1.390 +
1.391 + /// Executes the algorithm.
1.392 + bool start() {
1.393 + std::deque<Node> active_nodes;
1.394 + typename Graph::template NodeMap<bool> hyper(_graph, false);
1.395 +
1.396 + int node_num = countNodes(_graph);
1.397 + for ( ; _epsilon >= 1; _epsilon = _epsilon < ALPHA && _epsilon > 1 ?
1.398 + 1 : _epsilon / ALPHA )
1.399 + {
1.400 + // Performing price refinement heuristic using Bellman-Ford
1.401 + // algorithm
1.402 + if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) {
1.403 + typedef ShiftMap<ResidualCostMap> ShiftCostMap;
1.404 + ShiftCostMap shift_cost(_res_cost, _epsilon);
1.405 + BellmanFord<ResGraph, ShiftCostMap> bf(_res_graph, shift_cost);
1.406 + bf.init(0);
1.407 + bool done = false;
1.408 + int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(node_num));
1.409 + for (int i = 0; i < K && !done; ++i)
1.410 + done = bf.processNextWeakRound();
1.411 + if (done) {
1.412 + for (NodeIt n(_graph); n != INVALID; ++n)
1.413 + _potential[n] = bf.dist(n);
1.414 + continue;
1.415 + }
1.416 + }
1.417 +
1.418 + // Saturating edges not satisfying the optimality condition
1.419 + Capacity delta;
1.420 + for (EdgeIt e(_graph); e != INVALID; ++e) {
1.421 + if (_capacity[e] - _flow[e] > 0 && _red_cost[e] < 0) {
1.422 + delta = _capacity[e] - _flow[e];
1.423 + _excess[_graph.source(e)] -= delta;
1.424 + _excess[_graph.target(e)] += delta;
1.425 + _flow[e] = _capacity[e];
1.426 + }
1.427 + if (_flow[e] > 0 && -_red_cost[e] < 0) {
1.428 + _excess[_graph.target(e)] -= _flow[e];
1.429 + _excess[_graph.source(e)] += _flow[e];
1.430 + _flow[e] = 0;
1.431 + }
1.432 + }
1.433 +
1.434 + // Finding active nodes (i.e. nodes with positive excess)
1.435 + for (NodeIt n(_graph); n != INVALID; ++n)
1.436 + if (_excess[n] > 0) active_nodes.push_back(n);
1.437 +
1.438 + // Performing push and relabel operations
1.439 + while (active_nodes.size() > 0) {
1.440 + Node n = active_nodes[0], t;
1.441 + bool relabel_enabled = true;
1.442 +
1.443 + // Performing push operations if there are admissible edges
1.444 + if (_excess[n] > 0) {
1.445 + for (OutEdgeIt e(_graph, n); e != INVALID; ++e) {
1.446 + if (_capacity[e] - _flow[e] > 0 && _red_cost[e] < 0) {
1.447 + delta = _capacity[e] - _flow[e] <= _excess[n] ?
1.448 + _capacity[e] - _flow[e] : _excess[n];
1.449 + t = _graph.target(e);
1.450 +
1.451 + // Push-look-ahead heuristic
1.452 + Capacity ahead = -_excess[t];
1.453 + for (OutEdgeIt oe(_graph, t); oe != INVALID; ++oe) {
1.454 + if (_capacity[oe] - _flow[oe] > 0 && _red_cost[oe] < 0)
1.455 + ahead += _capacity[oe] - _flow[oe];
1.456 + }
1.457 + for (InEdgeIt ie(_graph, t); ie != INVALID; ++ie) {
1.458 + if (_flow[ie] > 0 && -_red_cost[ie] < 0)
1.459 + ahead += _flow[ie];
1.460 + }
1.461 + if (ahead < 0) ahead = 0;
1.462 +
1.463 + // Pushing flow along the edge
1.464 + if (ahead < delta) {
1.465 + _flow[e] += ahead;
1.466 + _excess[n] -= ahead;
1.467 + _excess[t] += ahead;
1.468 + active_nodes.push_front(t);
1.469 + hyper[t] = true;
1.470 + relabel_enabled = false;
1.471 + break;
1.472 + } else {
1.473 + _flow[e] += delta;
1.474 + _excess[n] -= delta;
1.475 + _excess[t] += delta;
1.476 + if (_excess[t] > 0 && _excess[t] <= delta)
1.477 + active_nodes.push_back(t);
1.478 + }
1.479 +
1.480 + if (_excess[n] == 0) break;
1.481 + }
1.482 + }
1.483 + }
1.484 +
1.485 + if (_excess[n] > 0) {
1.486 + for (InEdgeIt e(_graph, n); e != INVALID; ++e) {
1.487 + if (_flow[e] > 0 && -_red_cost[e] < 0) {
1.488 + delta = _flow[e] <= _excess[n] ? _flow[e] : _excess[n];
1.489 + t = _graph.source(e);
1.490 +
1.491 + // Push-look-ahead heuristic
1.492 + Capacity ahead = -_excess[t];
1.493 + for (OutEdgeIt oe(_graph, t); oe != INVALID; ++oe) {
1.494 + if (_capacity[oe] - _flow[oe] > 0 && _red_cost[oe] < 0)
1.495 + ahead += _capacity[oe] - _flow[oe];
1.496 + }
1.497 + for (InEdgeIt ie(_graph, t); ie != INVALID; ++ie) {
1.498 + if (_flow[ie] > 0 && -_red_cost[ie] < 0)
1.499 + ahead += _flow[ie];
1.500 + }
1.501 + if (ahead < 0) ahead = 0;
1.502 +
1.503 + // Pushing flow along the edge
1.504 + if (ahead < delta) {
1.505 + _flow[e] -= ahead;
1.506 + _excess[n] -= ahead;
1.507 + _excess[t] += ahead;
1.508 + active_nodes.push_front(t);
1.509 + hyper[t] = true;
1.510 + relabel_enabled = false;
1.511 + break;
1.512 + } else {
1.513 + _flow[e] -= delta;
1.514 + _excess[n] -= delta;
1.515 + _excess[t] += delta;
1.516 + if (_excess[t] > 0 && _excess[t] <= delta)
1.517 + active_nodes.push_back(t);
1.518 + }
1.519 +
1.520 + if (_excess[n] == 0) break;
1.521 + }
1.522 + }
1.523 + }
1.524 +
1.525 + if (relabel_enabled && (_excess[n] > 0 || hyper[n])) {
1.526 + // Performing relabel operation if the node is still active
1.527 + LCost min_red_cost = std::numeric_limits<LCost>::max();
1.528 + for (OutEdgeIt oe(_graph, n); oe != INVALID; ++oe) {
1.529 + if ( _capacity[oe] - _flow[oe] > 0 &&
1.530 + _red_cost[oe] < min_red_cost )
1.531 + min_red_cost = _red_cost[oe];
1.532 + }
1.533 + for (InEdgeIt ie(_graph, n); ie != INVALID; ++ie) {
1.534 + if (_flow[ie] > 0 && -_red_cost[ie] < min_red_cost)
1.535 + min_red_cost = -_red_cost[ie];
1.536 + }
1.537 + _potential[n] -= min_red_cost + _epsilon;
1.538 + hyper[n] = false;
1.539 + }
1.540 +
1.541 + // Removing active nodes with non-positive excess
1.542 + while ( active_nodes.size() > 0 &&
1.543 + _excess[active_nodes[0]] <= 0 &&
1.544 + !hyper[active_nodes[0]] ) {
1.545 + active_nodes.pop_front();
1.546 + }
1.547 + }
1.548 + }
1.549 +
1.550 + // Handling non-zero lower bounds
1.551 + if (_lower) {
1.552 + for (EdgeIt e(_graph); e != INVALID; ++e)
1.553 + _flow[e] += (*_lower)[e];
1.554 + }
1.555 + return true;
1.556 + }
1.557 +
1.558 + }; //class CostScaling
1.559 +
1.560 + ///@}
1.561 +
1.562 +} //namespace lemon
1.563 +
1.564 +#endif //LEMON_COST_SCALING_H