3 * This file is a part of LEMON, a generic C++ optimization library
5 * Copyright (C) 2003-2008
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_CAPACITY_SCALING_H
20 #define LEMON_CAPACITY_SCALING_H
22 /// \ingroup min_cost_flow_algs
25 /// \brief Capacity Scaling algorithm for finding a minimum cost flow.
29 #include <lemon/core.h>
30 #include <lemon/bin_heap.h>
34 /// \brief Default traits class of CapacityScaling algorithm.
36 /// Default traits class of CapacityScaling algorithm.
37 /// \tparam GR Digraph type.
38 /// \tparam V The number type used for flow amounts, capacity bounds
39 /// and supply values. By default it is \c int.
40 /// \tparam C The number type used for costs and potentials.
41 /// By default it is the same as \c V.
42 template <typename GR, typename V = int, typename C = V>
43 struct CapacityScalingDefaultTraits
45 /// The type of the digraph
47 /// The type of the flow amounts, capacity bounds and supply values
49 /// The type of the arc costs
52 /// \brief The type of the heap used for internal Dijkstra computations.
54 /// The type of the heap used for internal Dijkstra computations.
55 /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
56 /// its priority type must be \c Cost and its cross reference type
57 /// must be \ref RangeMap "RangeMap<int>".
58 typedef BinHeap<Cost, RangeMap<int> > Heap;
61 /// \addtogroup min_cost_flow_algs
64 /// \brief Implementation of the Capacity Scaling algorithm for
65 /// finding a \ref min_cost_flow "minimum cost flow".
67 /// \ref CapacityScaling implements the capacity scaling version
68 /// of the successive shortest path algorithm for finding a
69 /// \ref min_cost_flow "minimum cost flow" \ref amo93networkflows,
70 /// \ref edmondskarp72theoretical. It is an efficient dual
73 /// Most of the parameters of the problem (except for the digraph)
74 /// can be given using separate functions, and the algorithm can be
75 /// executed using the \ref run() function. If some parameters are not
76 /// specified, then default values will be used.
78 /// \tparam GR The digraph type the algorithm runs on.
79 /// \tparam V The number type used for flow amounts, capacity bounds
80 /// and supply values in the algorithm. By default it is \c int.
81 /// \tparam C The number type used for costs and potentials in the
82 /// algorithm. By default it is the same as \c V.
84 /// \warning Both number types must be signed and all input data must
86 /// \warning This algorithm does not support negative costs for such
87 /// arcs that have infinite upper bound.
89 template <typename GR, typename V, typename C, typename TR>
91 template < typename GR, typename V = int, typename C = V,
92 typename TR = CapacityScalingDefaultTraits<GR, V, C> >
98 /// The type of the digraph
99 typedef typename TR::Digraph Digraph;
100 /// The type of the flow amounts, capacity bounds and supply values
101 typedef typename TR::Value Value;
102 /// The type of the arc costs
103 typedef typename TR::Cost Cost;
105 /// The type of the heap used for internal Dijkstra computations
106 typedef typename TR::Heap Heap;
108 /// The \ref CapacityScalingDefaultTraits "traits class" of the algorithm
113 /// \brief Problem type constants for the \c run() function.
115 /// Enum type containing the problem type constants that can be
116 /// returned by the \ref run() function of the algorithm.
118 /// The problem has no feasible solution (flow).
120 /// The problem has optimal solution (i.e. it is feasible and
121 /// bounded), and the algorithm has found optimal flow and node
122 /// potentials (primal and dual solutions).
124 /// The digraph contains an arc of negative cost and infinite
125 /// upper bound. It means that the objective function is unbounded
126 /// on that arc, however, note that it could actually be bounded
127 /// over the feasible flows, but this algroithm cannot handle
134 TEMPLATE_DIGRAPH_TYPEDEFS(GR);
136 typedef std::vector<int> IntVector;
137 typedef std::vector<char> BoolVector;
138 typedef std::vector<Value> ValueVector;
139 typedef std::vector<Cost> CostVector;
143 // Data related to the underlying digraph
150 // Parameters of the problem
154 // Data structures for storing the digraph
158 IntVector _first_out;
170 ValueVector _res_cap;
173 IntVector _excess_nodes;
174 IntVector _deficit_nodes;
182 /// \brief Constant for infinite upper bounds (capacities).
184 /// Constant for infinite upper bounds (capacities).
185 /// It is \c std::numeric_limits<Value>::infinity() if available,
186 /// \c std::numeric_limits<Value>::max() otherwise.
191 // Special implementation of the Dijkstra algorithm for finding
192 // shortest paths in the residual network of the digraph with
193 // respect to the reduced arc costs and modifying the node
194 // potentials according to the found distance labels.
195 class ResidualDijkstra
201 const IntVector &_first_out;
202 const IntVector &_target;
203 const CostVector &_cost;
204 const ValueVector &_res_cap;
205 const ValueVector &_excess;
209 IntVector _proc_nodes;
214 ResidualDijkstra(CapacityScaling& cs) :
215 _node_num(cs._node_num), _geq(cs._sum_supply < 0),
216 _first_out(cs._first_out), _target(cs._target), _cost(cs._cost),
217 _res_cap(cs._res_cap), _excess(cs._excess), _pi(cs._pi),
218 _pred(cs._pred), _dist(cs._node_num)
221 int run(int s, Value delta = 1) {
222 RangeMap<int> heap_cross_ref(_node_num, Heap::PRE_HEAP);
223 Heap heap(heap_cross_ref);
229 while (!heap.empty() && _excess[heap.top()] > -delta) {
230 int u = heap.top(), v;
231 Cost d = heap.prio() + _pi[u], dn;
232 _dist[u] = heap.prio();
233 _proc_nodes.push_back(u);
236 // Traverse outgoing residual arcs
237 int last_out = _geq ? _first_out[u+1] : _first_out[u+1] - 1;
238 for (int a = _first_out[u]; a != last_out; ++a) {
239 if (_res_cap[a] < delta) continue;
241 switch (heap.state(v)) {
243 heap.push(v, d + _cost[a] - _pi[v]);
247 dn = d + _cost[a] - _pi[v];
249 heap.decrease(v, dn);
253 case Heap::POST_HEAP:
258 if (heap.empty()) return -1;
260 // Update potentials of processed nodes
262 Cost dt = heap.prio();
263 for (int i = 0; i < int(_proc_nodes.size()); ++i) {
264 _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]] - dt;
270 }; //class ResidualDijkstra
274 /// \name Named Template Parameters
277 template <typename T>
278 struct SetHeapTraits : public Traits {
282 /// \brief \ref named-templ-param "Named parameter" for setting
285 /// \ref named-templ-param "Named parameter" for setting \c Heap
286 /// type, which is used for internal Dijkstra computations.
287 /// It must conform to the \ref lemon::concepts::Heap "Heap" concept,
288 /// its priority type must be \c Cost and its cross reference type
289 /// must be \ref RangeMap "RangeMap<int>".
290 template <typename T>
292 : public CapacityScaling<GR, V, C, SetHeapTraits<T> > {
293 typedef CapacityScaling<GR, V, C, SetHeapTraits<T> > Create;
300 /// \brief Constructor.
302 /// The constructor of the class.
304 /// \param graph The digraph the algorithm runs on.
305 CapacityScaling(const GR& graph) :
306 _graph(graph), _node_id(graph), _arc_idf(graph), _arc_idb(graph),
307 INF(std::numeric_limits<Value>::has_infinity ?
308 std::numeric_limits<Value>::infinity() :
309 std::numeric_limits<Value>::max())
311 // Check the number types
312 LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
313 "The flow type of CapacityScaling must be signed");
314 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
315 "The cost type of CapacityScaling must be signed");
317 // Reset data structures
322 /// The parameters of the algorithm can be specified using these
327 /// \brief Set the lower bounds on the arcs.
329 /// This function sets the lower bounds on the arcs.
330 /// If it is not used before calling \ref run(), the lower bounds
331 /// will be set to zero on all arcs.
333 /// \param map An arc map storing the lower bounds.
334 /// Its \c Value type must be convertible to the \c Value type
335 /// of the algorithm.
337 /// \return <tt>(*this)</tt>
338 template <typename LowerMap>
339 CapacityScaling& lowerMap(const LowerMap& map) {
341 for (ArcIt a(_graph); a != INVALID; ++a) {
342 _lower[_arc_idf[a]] = map[a];
343 _lower[_arc_idb[a]] = map[a];
348 /// \brief Set the upper bounds (capacities) on the arcs.
350 /// This function sets the upper bounds (capacities) on the arcs.
351 /// If it is not used before calling \ref run(), the upper bounds
352 /// will be set to \ref INF on all arcs (i.e. the flow value will be
353 /// unbounded from above).
355 /// \param map An arc map storing the upper bounds.
356 /// Its \c Value type must be convertible to the \c Value type
357 /// of the algorithm.
359 /// \return <tt>(*this)</tt>
360 template<typename UpperMap>
361 CapacityScaling& upperMap(const UpperMap& map) {
362 for (ArcIt a(_graph); a != INVALID; ++a) {
363 _upper[_arc_idf[a]] = map[a];
368 /// \brief Set the costs of the arcs.
370 /// This function sets the costs of the arcs.
371 /// If it is not used before calling \ref run(), the costs
372 /// will be set to \c 1 on all arcs.
374 /// \param map An arc map storing the costs.
375 /// Its \c Value type must be convertible to the \c Cost type
376 /// of the algorithm.
378 /// \return <tt>(*this)</tt>
379 template<typename CostMap>
380 CapacityScaling& costMap(const CostMap& map) {
381 for (ArcIt a(_graph); a != INVALID; ++a) {
382 _cost[_arc_idf[a]] = map[a];
383 _cost[_arc_idb[a]] = -map[a];
388 /// \brief Set the supply values of the nodes.
390 /// This function sets the supply values of the nodes.
391 /// If neither this function nor \ref stSupply() is used before
392 /// calling \ref run(), the supply of each node will be set to zero.
394 /// \param map A node map storing the supply values.
395 /// Its \c Value type must be convertible to the \c Value type
396 /// of the algorithm.
398 /// \return <tt>(*this)</tt>
399 template<typename SupplyMap>
400 CapacityScaling& supplyMap(const SupplyMap& map) {
401 for (NodeIt n(_graph); n != INVALID; ++n) {
402 _supply[_node_id[n]] = map[n];
407 /// \brief Set single source and target nodes and a supply value.
409 /// This function sets a single source node and a single target node
410 /// and the required flow value.
411 /// If neither this function nor \ref supplyMap() is used before
412 /// calling \ref run(), the supply of each node will be set to zero.
414 /// Using this function has the same effect as using \ref supplyMap()
415 /// with such a map in which \c k is assigned to \c s, \c -k is
416 /// assigned to \c t and all other nodes have zero supply value.
418 /// \param s The source node.
419 /// \param t The target node.
420 /// \param k The required amount of flow from node \c s to node \c t
421 /// (i.e. the supply of \c s and the demand of \c t).
423 /// \return <tt>(*this)</tt>
424 CapacityScaling& stSupply(const Node& s, const Node& t, Value k) {
425 for (int i = 0; i != _node_num; ++i) {
428 _supply[_node_id[s]] = k;
429 _supply[_node_id[t]] = -k;
435 /// \name Execution control
436 /// The algorithm can be executed using \ref run().
440 /// \brief Run the algorithm.
442 /// This function runs the algorithm.
443 /// The paramters can be specified using functions \ref lowerMap(),
444 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
447 /// CapacityScaling<ListDigraph> cs(graph);
448 /// cs.lowerMap(lower).upperMap(upper).costMap(cost)
449 /// .supplyMap(sup).run();
452 /// This function can be called more than once. All the given parameters
453 /// are kept for the next call, unless \ref resetParams() or \ref reset()
454 /// is used, thus only the modified parameters have to be set again.
455 /// If the underlying digraph was also modified after the construction
456 /// of the class (or the last \ref reset() call), then the \ref reset()
457 /// function must be called.
459 /// \param factor The capacity scaling factor. It must be larger than
460 /// one to use scaling. If it is less or equal to one, then scaling
461 /// will be disabled.
463 /// \return \c INFEASIBLE if no feasible flow exists,
464 /// \n \c OPTIMAL if the problem has optimal solution
465 /// (i.e. it is feasible and bounded), and the algorithm has found
466 /// optimal flow and node potentials (primal and dual solutions),
467 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost
468 /// and infinite upper bound. It means that the objective function
469 /// is unbounded on that arc, however, note that it could actually be
470 /// bounded over the feasible flows, but this algroithm cannot handle
474 /// \see resetParams(), reset()
475 ProblemType run(int factor = 4) {
477 ProblemType pt = init();
478 if (pt != OPTIMAL) return pt;
482 /// \brief Reset all the parameters that have been given before.
484 /// This function resets all the paramaters that have been given
485 /// before using functions \ref lowerMap(), \ref upperMap(),
486 /// \ref costMap(), \ref supplyMap(), \ref stSupply().
488 /// It is useful for multiple \ref run() calls. Basically, all the given
489 /// parameters are kept for the next \ref run() call, unless
490 /// \ref resetParams() or \ref reset() is used.
491 /// If the underlying digraph was also modified after the construction
492 /// of the class or the last \ref reset() call, then the \ref reset()
493 /// function must be used, otherwise \ref resetParams() is sufficient.
497 /// CapacityScaling<ListDigraph> cs(graph);
500 /// cs.lowerMap(lower).upperMap(upper).costMap(cost)
501 /// .supplyMap(sup).run();
503 /// // Run again with modified cost map (resetParams() is not called,
504 /// // so only the cost map have to be set again)
506 /// cs.costMap(cost).run();
508 /// // Run again from scratch using resetParams()
509 /// // (the lower bounds will be set to zero on all arcs)
510 /// cs.resetParams();
511 /// cs.upperMap(capacity).costMap(cost)
512 /// .supplyMap(sup).run();
515 /// \return <tt>(*this)</tt>
517 /// \see reset(), run()
518 CapacityScaling& resetParams() {
519 for (int i = 0; i != _node_num; ++i) {
522 for (int j = 0; j != _res_arc_num; ++j) {
525 _cost[j] = _forward[j] ? 1 : -1;
531 /// \brief Reset the internal data structures and all the parameters
532 /// that have been given before.
534 /// This function resets the internal data structures and all the
535 /// paramaters that have been given before using functions \ref lowerMap(),
536 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().
538 /// It is useful for multiple \ref run() calls. Basically, all the given
539 /// parameters are kept for the next \ref run() call, unless
540 /// \ref resetParams() or \ref reset() is used.
541 /// If the underlying digraph was also modified after the construction
542 /// of the class or the last \ref reset() call, then the \ref reset()
543 /// function must be used, otherwise \ref resetParams() is sufficient.
545 /// See \ref resetParams() for examples.
547 /// \return <tt>(*this)</tt>
549 /// \see resetParams(), run()
550 CapacityScaling& reset() {
552 _node_num = countNodes(_graph);
553 _arc_num = countArcs(_graph);
554 _res_arc_num = 2 * (_arc_num + _node_num);
558 _first_out.resize(_node_num + 1);
559 _forward.resize(_res_arc_num);
560 _source.resize(_res_arc_num);
561 _target.resize(_res_arc_num);
562 _reverse.resize(_res_arc_num);
564 _lower.resize(_res_arc_num);
565 _upper.resize(_res_arc_num);
566 _cost.resize(_res_arc_num);
567 _supply.resize(_node_num);
569 _res_cap.resize(_res_arc_num);
570 _pi.resize(_node_num);
571 _excess.resize(_node_num);
572 _pred.resize(_node_num);
575 int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;
576 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
580 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
582 for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {
586 _target[j] = _node_id[_graph.runningNode(a)];
588 for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {
592 _target[j] = _node_id[_graph.runningNode(a)];
605 _first_out[_node_num] = k;
606 for (ArcIt a(_graph); a != INVALID; ++a) {
607 int fi = _arc_idf[a];
608 int bi = _arc_idb[a];
620 /// \name Query Functions
621 /// The results of the algorithm can be obtained using these
623 /// The \ref run() function must be called before using them.
627 /// \brief Return the total cost of the found flow.
629 /// This function returns the total cost of the found flow.
630 /// Its complexity is O(e).
632 /// \note The return type of the function can be specified as a
633 /// template parameter. For example,
635 /// cs.totalCost<double>();
637 /// It is useful if the total cost cannot be stored in the \c Cost
638 /// type of the algorithm, which is the default return type of the
641 /// \pre \ref run() must be called before using this function.
642 template <typename Number>
643 Number totalCost() const {
645 for (ArcIt a(_graph); a != INVALID; ++a) {
647 c += static_cast<Number>(_res_cap[i]) *
648 (-static_cast<Number>(_cost[i]));
654 Cost totalCost() const {
655 return totalCost<Cost>();
659 /// \brief Return the flow on the given arc.
661 /// This function returns the flow on the given arc.
663 /// \pre \ref run() must be called before using this function.
664 Value flow(const Arc& a) const {
665 return _res_cap[_arc_idb[a]];
668 /// \brief Return the flow map (the primal solution).
670 /// This function copies the flow value on each arc into the given
671 /// map. The \c Value type of the algorithm must be convertible to
672 /// the \c Value type of the map.
674 /// \pre \ref run() must be called before using this function.
675 template <typename FlowMap>
676 void flowMap(FlowMap &map) const {
677 for (ArcIt a(_graph); a != INVALID; ++a) {
678 map.set(a, _res_cap[_arc_idb[a]]);
682 /// \brief Return the potential (dual value) of the given node.
684 /// This function returns the potential (dual value) of the
687 /// \pre \ref run() must be called before using this function.
688 Cost potential(const Node& n) const {
689 return _pi[_node_id[n]];
692 /// \brief Return the potential map (the dual solution).
694 /// This function copies the potential (dual value) of each node
695 /// into the given map.
696 /// The \c Cost type of the algorithm must be convertible to the
697 /// \c Value type of the map.
699 /// \pre \ref run() must be called before using this function.
700 template <typename PotentialMap>
701 void potentialMap(PotentialMap &map) const {
702 for (NodeIt n(_graph); n != INVALID; ++n) {
703 map.set(n, _pi[_node_id[n]]);
711 // Initialize the algorithm
713 if (_node_num <= 1) return INFEASIBLE;
715 // Check the sum of supply values
717 for (int i = 0; i != _root; ++i) {
718 _sum_supply += _supply[i];
720 if (_sum_supply > 0) return INFEASIBLE;
722 // Initialize vectors
723 for (int i = 0; i != _root; ++i) {
725 _excess[i] = _supply[i];
728 // Remove non-zero lower bounds
729 const Value MAX = std::numeric_limits<Value>::max();
732 for (int i = 0; i != _root; ++i) {
733 last_out = _first_out[i+1];
734 for (int j = _first_out[i]; j != last_out; ++j) {
738 _res_cap[j] = _upper[j] < MAX ? _upper[j] - c : INF;
740 _res_cap[j] = _upper[j] < MAX + c ? _upper[j] - c : INF;
743 _excess[_target[j]] += c;
750 for (int j = 0; j != _res_arc_num; ++j) {
751 _res_cap[j] = _forward[j] ? _upper[j] : 0;
755 // Handle negative costs
756 for (int i = 0; i != _root; ++i) {
757 last_out = _first_out[i+1] - 1;
758 for (int j = _first_out[i]; j != last_out; ++j) {
759 Value rc = _res_cap[j];
760 if (_cost[j] < 0 && rc > 0) {
761 if (rc >= MAX) return UNBOUNDED;
763 _excess[_target[j]] += rc;
765 _res_cap[_reverse[j]] += rc;
770 // Handle GEQ supply type
771 if (_sum_supply < 0) {
773 _excess[_root] = -_sum_supply;
774 for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
775 int ra = _reverse[a];
776 _res_cap[a] = -_sum_supply + 1;
784 for (int a = _first_out[_root]; a != _res_arc_num; ++a) {
785 int ra = _reverse[a];
793 // Initialize delta value
796 Value max_sup = 0, max_dem = 0;
797 for (int i = 0; i != _node_num; ++i) {
798 Value ex = _excess[i];
799 if ( ex > max_sup) max_sup = ex;
800 if (-ex > max_dem) max_dem = -ex;
803 for (int j = 0; j != _res_arc_num; ++j) {
804 if (_res_cap[j] > max_cap) max_cap = _res_cap[j];
806 max_sup = std::min(std::min(max_sup, max_dem), max_cap);
807 for (_delta = 1; 2 * _delta <= max_sup; _delta *= 2) ;
816 ProblemType start() {
817 // Execute the algorithm
820 pt = startWithScaling();
822 pt = startWithoutScaling();
824 // Handle non-zero lower bounds
826 int limit = _first_out[_root];
827 for (int j = 0; j != limit; ++j) {
828 if (!_forward[j]) _res_cap[j] += _lower[j];
832 // Shift potentials if necessary
833 Cost pr = _pi[_root];
834 if (_sum_supply < 0 || pr > 0) {
835 for (int i = 0; i != _node_num; ++i) {
843 // Execute the capacity scaling algorithm
844 ProblemType startWithScaling() {
845 // Perform capacity scaling phases
847 ResidualDijkstra _dijkstra(*this);
849 // Saturate all arcs not satisfying the optimality condition
851 for (int u = 0; u != _node_num; ++u) {
852 last_out = _sum_supply < 0 ?
853 _first_out[u+1] : _first_out[u+1] - 1;
854 for (int a = _first_out[u]; a != last_out; ++a) {
856 Cost c = _cost[a] + _pi[u] - _pi[v];
857 Value rc = _res_cap[a];
858 if (c < 0 && rc >= _delta) {
862 _res_cap[_reverse[a]] += rc;
867 // Find excess nodes and deficit nodes
868 _excess_nodes.clear();
869 _deficit_nodes.clear();
870 for (int u = 0; u != _node_num; ++u) {
871 Value ex = _excess[u];
872 if (ex >= _delta) _excess_nodes.push_back(u);
873 if (ex <= -_delta) _deficit_nodes.push_back(u);
875 int next_node = 0, next_def_node = 0;
877 // Find augmenting shortest paths
878 while (next_node < int(_excess_nodes.size())) {
879 // Check deficit nodes
881 bool delta_deficit = false;
882 for ( ; next_def_node < int(_deficit_nodes.size());
884 if (_excess[_deficit_nodes[next_def_node]] <= -_delta) {
885 delta_deficit = true;
889 if (!delta_deficit) break;
892 // Run Dijkstra in the residual network
893 s = _excess_nodes[next_node];
894 if ((t = _dijkstra.run(s, _delta)) == -1) {
902 // Augment along a shortest path from s to t
903 Value d = std::min(_excess[s], -_excess[t]);
907 while ((a = _pred[u]) != -1) {
908 if (_res_cap[a] < d) d = _res_cap[a];
913 while ((a = _pred[u]) != -1) {
915 _res_cap[_reverse[a]] += d;
921 if (_excess[s] < _delta) ++next_node;
924 if (_delta == 1) break;
925 _delta = _delta <= _factor ? 1 : _delta / _factor;
931 // Execute the successive shortest path algorithm
932 ProblemType startWithoutScaling() {
934 _excess_nodes.clear();
935 for (int i = 0; i != _node_num; ++i) {
936 if (_excess[i] > 0) _excess_nodes.push_back(i);
938 if (_excess_nodes.size() == 0) return OPTIMAL;
941 // Find shortest paths
943 ResidualDijkstra _dijkstra(*this);
944 while ( _excess[_excess_nodes[next_node]] > 0 ||
945 ++next_node < int(_excess_nodes.size()) )
947 // Run Dijkstra in the residual network
948 s = _excess_nodes[next_node];
949 if ((t = _dijkstra.run(s)) == -1) return INFEASIBLE;
951 // Augment along a shortest path from s to t
952 Value d = std::min(_excess[s], -_excess[t]);
956 while ((a = _pred[u]) != -1) {
957 if (_res_cap[a] < d) d = _res_cap[a];
962 while ((a = _pred[u]) != -1) {
964 _res_cap[_reverse[a]] += d;
974 }; //class CapacityScaling
980 #endif //LEMON_CAPACITY_SCALING_H