COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/capacity_scaling.h @ 2457:8c791ee69a45

Last change on this file since 2457:8c791ee69a45 was 2457:8c791ee69a45, checked in by Balazs Dezso, 12 years ago

Improvments in min cost flow algorithms

  • improved cycle cancelling
File size: 20.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2007
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
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.
12 *
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
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_CAPACITY_SCALING_H
20#define LEMON_CAPACITY_SCALING_H
21
22/// \ingroup min_cost_flow
23///
24/// \file
25/// \brief The capacity scaling algorithm for finding a minimum cost
26/// flow.
27
28#include <vector>
29#include <lemon/dijkstra.h>
30#include <lemon/graph_adaptor.h>
31
32#define WITH_SCALING
33
34//#define _DEBUG_ITER_
35
36namespace lemon {
37
38  /// \addtogroup min_cost_flow
39  /// @{
40
41  /// \brief Implementation of the capacity scaling version of the
42  /// successive shortest path algorithm for finding a minimum cost flow.
43  ///
44  /// \ref lemon::CapacityScaling "CapacityScaling" implements a
45  /// capacity scaling algorithm for finding a minimum cost flow.
46  ///
47  /// \param Graph The directed graph type the algorithm runs on.
48  /// \param LowerMap The type of the lower bound map.
49  /// \param CapacityMap The type of the capacity (upper bound) map.
50  /// \param CostMap The type of the cost (length) map.
51  /// \param SupplyMap The type of the supply map.
52  ///
53  /// \warning
54  /// - Edge capacities and costs should be nonnegative integers.
55  ///   However \c CostMap::Value should be signed type.
56  /// - Supply values should be integers.
57  /// - \c LowerMap::Value must be convertible to
58  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
59  ///   convertible to \c SupplyMap::Value.
60  ///
61  /// \author Peter Kovacs
62
63template < typename Graph,
64           typename LowerMap = typename Graph::template EdgeMap<int>,
65           typename CapacityMap = LowerMap,
66           typename CostMap = typename Graph::template EdgeMap<int>,
67           typename SupplyMap = typename Graph::template NodeMap
68                                <typename CapacityMap::Value> >
69  class CapacityScaling
70  {
71    typedef typename Graph::Node Node;
72    typedef typename Graph::NodeIt NodeIt;
73    typedef typename Graph::Edge Edge;
74    typedef typename Graph::EdgeIt EdgeIt;
75    typedef typename Graph::InEdgeIt InEdgeIt;
76    typedef typename Graph::OutEdgeIt OutEdgeIt;
77
78    typedef typename LowerMap::Value Lower;
79    typedef typename CapacityMap::Value Capacity;
80    typedef typename CostMap::Value Cost;
81    typedef typename SupplyMap::Value Supply;
82    typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
83    typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
84
85    typedef ResGraphAdaptor< const Graph, Capacity,
86                             CapacityRefMap, CapacityRefMap > ResGraph;
87    typedef typename ResGraph::Node ResNode;
88    typedef typename ResGraph::NodeIt ResNodeIt;
89    typedef typename ResGraph::Edge ResEdge;
90    typedef typename ResGraph::EdgeIt ResEdgeIt;
91
92  public:
93
94    /// \brief The type of the flow map.
95    typedef CapacityRefMap FlowMap;
96    /// \brief The type of the potential map.
97    typedef typename Graph::template NodeMap<Cost> PotentialMap;
98
99  protected:
100
101    /// \brief Map adaptor class for handling reduced edge costs.
102    class ReducedCostMap : public MapBase<ResEdge, Cost>
103    {
104    private:
105
106      const ResGraph &gr;
107      const CostMap &cost_map;
108      const PotentialMap &pot_map;
109
110    public:
111
112      typedef typename MapBase<ResEdge, Cost>::Value Value;
113      typedef typename MapBase<ResEdge, Cost>::Key Key;
114
115      ReducedCostMap( const ResGraph &_gr,
116                      const CostMap &_cost,
117                      const PotentialMap &_pot ) :
118        gr(_gr), cost_map(_cost), pot_map(_pot) {}
119
120      Value operator[](const Key &e) const {
121        return ResGraph::forward(e) ?
122           cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)] :
123          -cost_map[e] - pot_map[gr.source(e)] + pot_map[gr.target(e)];
124      }
125
126    }; //class ReducedCostMap
127
128    /// \brief Map adaptor for \ref lemon::Dijkstra "Dijkstra" class to
129    /// update node potentials.
130    class PotentialUpdateMap : public MapBase<ResNode, Cost>
131    {
132    private:
133
134      PotentialMap *pot;
135      typedef std::pair<ResNode, Cost> Pair;
136      std::vector<Pair> data;
137
138    public:
139
140      typedef typename MapBase<ResNode, Cost>::Value Value;
141      typedef typename MapBase<ResNode, Cost>::Key Key;
142
143      void potentialMap(PotentialMap &_pot) {
144        pot = &_pot;
145      }
146
147      void init() {
148        data.clear();
149      }
150
151      void set(const Key &n, const Value &v) {
152        data.push_back(Pair(n, v));
153      }
154
155      void update() {
156        Cost val = data[data.size()-1].second;
157        for (int i = 0; i < data.size()-1; ++i)
158          (*pot)[data[i].first] += val - data[i].second;
159      }
160
161    }; //class PotentialUpdateMap
162
163#ifdef WITH_SCALING
164    /// \brief Map adaptor class for identifing deficit nodes.
165    class DeficitBoolMap : public MapBase<ResNode, bool>
166    {
167    private:
168
169      const SupplyRefMap &imb;
170      const Capacity &delta;
171
172    public:
173
174      DeficitBoolMap(const SupplyRefMap &_imb, const Capacity &_delta) :
175        imb(_imb), delta(_delta) {}
176
177      bool operator[](const ResNode &n) const {
178        return imb[n] <= -delta;
179      }
180
181    }; //class DeficitBoolMap
182
183    /// \brief Map adaptor class for filtering edges with at least
184    /// \c delta residual capacity
185    class DeltaFilterMap : public MapBase<ResEdge, bool>
186    {
187    private:
188
189      const ResGraph &gr;
190      const Capacity &delta;
191
192    public:
193
194      typedef typename MapBase<ResEdge, Cost>::Value Value;
195      typedef typename MapBase<ResEdge, Cost>::Key Key;
196
197      DeltaFilterMap(const ResGraph &_gr, const Capacity &_delta) :
198        gr(_gr), delta(_delta) {}
199
200      Value operator[](const Key &e) const {
201        return gr.rescap(e) >= delta;
202      }
203
204    }; //class DeltaFilterMap
205
206    typedef EdgeSubGraphAdaptor<const ResGraph, const DeltaFilterMap>
207      DeltaResGraph;
208
209    /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class.
210    class ResDijkstraTraits :
211      public DijkstraDefaultTraits<DeltaResGraph, ReducedCostMap>
212    {
213    public:
214
215      typedef PotentialUpdateMap DistMap;
216
217      static DistMap *createDistMap(const DeltaResGraph&) {
218        return new DistMap();
219      }
220
221    }; //class ResDijkstraTraits
222
223#else //WITHOUT_CAPACITY_SCALING
224    /// \brief Map adaptor class for identifing deficit nodes.
225    class DeficitBoolMap : public MapBase<ResNode, bool>
226    {
227    private:
228
229      const SupplyRefMap &imb;
230
231    public:
232
233      DeficitBoolMap(const SupplyRefMap &_imb) : imb(_imb) {}
234
235      bool operator[](const ResNode &n) const {
236        return imb[n] < 0;
237      }
238
239    }; //class DeficitBoolMap
240
241    /// \brief Traits class for \ref lemon::Dijkstra "Dijkstra" class.
242    class ResDijkstraTraits :
243      public DijkstraDefaultTraits<ResGraph, ReducedCostMap>
244    {
245    public:
246
247      typedef PotentialUpdateMap DistMap;
248
249      static DistMap *createDistMap(const ResGraph&) {
250        return new DistMap();
251      }
252
253    }; //class ResDijkstraTraits
254#endif
255
256  protected:
257
258    /// \brief The directed graph the algorithm runs on.
259    const Graph &graph;
260    /// \brief The original lower bound map.
261    const LowerMap *lower;
262    /// \brief The modified capacity map.
263    CapacityRefMap capacity;
264    /// \brief The cost map.
265    const CostMap &cost;
266    /// \brief The modified supply map.
267    SupplyRefMap supply;
268    /// \brief The sum of supply values equals zero.
269    bool valid_supply;
270
271    /// \brief The edge map of the current flow.
272    FlowMap flow;
273    /// \brief The potential node map.
274    PotentialMap potential;
275    /// \brief The residual graph.
276    ResGraph res_graph;
277    /// \brief The reduced cost map.
278    ReducedCostMap red_cost;
279
280    /// \brief The imbalance map.
281    SupplyRefMap imbalance;
282    /// \brief The excess nodes.
283    std::vector<ResNode> excess_nodes;
284    /// \brief The index of the next excess node.
285    int next_node;
286
287#ifdef WITH_SCALING
288    typedef Dijkstra<DeltaResGraph, ReducedCostMap, ResDijkstraTraits>
289      ResDijkstra;
290    /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding
291    /// shortest paths in the residual graph with respect to the
292    /// reduced edge costs.
293    ResDijkstra dijkstra;
294
295    /// \brief The delta parameter used for capacity scaling.
296    Capacity delta;
297    /// \brief Edge filter map.
298    DeltaFilterMap delta_filter;
299    /// \brief The delta residual graph.
300    DeltaResGraph dres_graph;
301    /// \brief Map for identifing deficit nodes.
302    DeficitBoolMap delta_deficit;
303
304    /// \brief The deficit nodes.
305    std::vector<ResNode> deficit_nodes;
306
307#else //WITHOUT_CAPACITY_SCALING
308    typedef Dijkstra<ResGraph, ReducedCostMap, ResDijkstraTraits>
309      ResDijkstra;
310    /// \brief \ref lemon::Dijkstra "Dijkstra" class for finding
311    /// shortest paths in the residual graph with respect to the
312    /// reduced edge costs.
313    ResDijkstra dijkstra;
314    /// \brief Map for identifing deficit nodes.
315    DeficitBoolMap has_deficit;
316#endif
317
318    /// \brief Pred map for the \ref lemon::Dijkstra "Dijkstra" class.
319    typename ResDijkstra::PredMap pred;
320    /// \brief Dist map for the \ref lemon::Dijkstra "Dijkstra" class to
321    /// update node potentials.
322    PotentialUpdateMap updater;
323
324  public :
325
326    /// \brief General constructor of the class (with lower bounds).
327    ///
328    /// General constructor of the class (with lower bounds).
329    ///
330    /// \param _graph The directed graph the algorithm runs on.
331    /// \param _lower The lower bounds of the edges.
332    /// \param _capacity The capacities (upper bounds) of the edges.
333    /// \param _cost The cost (length) values of the edges.
334    /// \param _supply The supply values of the nodes (signed).
335    CapacityScaling( const Graph &_graph,
336                     const LowerMap &_lower,
337                     const CapacityMap &_capacity,
338                     const CostMap &_cost,
339                     const SupplyMap &_supply ) :
340      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
341      supply(_graph), flow(_graph, 0), potential(_graph, 0),
342      res_graph(_graph, capacity, flow),
343      red_cost(res_graph, cost, potential), imbalance(_graph),
344#ifdef WITH_SCALING
345      delta(0), delta_filter(res_graph, delta),
346      dres_graph(res_graph, delta_filter),
347      dijkstra(dres_graph, red_cost), pred(dres_graph),
348      delta_deficit(imbalance, delta)
349#else //WITHOUT_CAPACITY_SCALING
350      dijkstra(res_graph, red_cost), pred(res_graph),
351      has_deficit(imbalance)
352#endif
353    {
354      // Removing nonzero lower bounds
355      capacity = subMap(_capacity, _lower);
356      Supply sum = 0;
357      for (NodeIt n(graph); n != INVALID; ++n) {
358        Supply s = _supply[n];
359        for (InEdgeIt e(graph, n); e != INVALID; ++e)
360          s += _lower[e];
361        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
362          s -= _lower[e];
363        supply[n] = imbalance[n] = s;
364        sum += s;
365      }
366      valid_supply = sum == 0;
367    }
368
369    /// \brief General constructor of the class (without lower bounds).
370    ///
371    /// General constructor of the class (without lower bounds).
372    ///
373    /// \param _graph The directed graph the algorithm runs on.
374    /// \param _capacity The capacities (upper bounds) of the edges.
375    /// \param _cost The cost (length) values of the edges.
376    /// \param _supply The supply values of the nodes (signed).
377    CapacityScaling( const Graph &_graph,
378                     const CapacityMap &_capacity,
379                     const CostMap &_cost,
380                     const SupplyMap &_supply ) :
381      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
382      supply(_supply), flow(_graph, 0), potential(_graph, 0),
383      res_graph(_graph, capacity, flow),
384      red_cost(res_graph, cost, potential), imbalance(_graph),
385#ifdef WITH_SCALING
386      delta(0), delta_filter(res_graph, delta),
387      dres_graph(res_graph, delta_filter),
388      dijkstra(dres_graph, red_cost), pred(dres_graph),
389      delta_deficit(imbalance, delta)
390#else //WITHOUT_CAPACITY_SCALING
391      dijkstra(res_graph, red_cost), pred(res_graph),
392      has_deficit(imbalance)
393#endif
394    {
395      // Checking the sum of supply values
396      Supply sum = 0;
397      for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
398      valid_supply = sum == 0;
399    }
400
401    /// \brief Simple constructor of the class (with lower bounds).
402    ///
403    /// Simple constructor of the class (with lower bounds).
404    ///
405    /// \param _graph The directed graph the algorithm runs on.
406    /// \param _lower The lower bounds of the edges.
407    /// \param _capacity The capacities (upper bounds) of the edges.
408    /// \param _cost The cost (length) values of the edges.
409    /// \param _s The source node.
410    /// \param _t The target node.
411    /// \param _flow_value The required amount of flow from node \c _s
412    /// to node \c _t (i.e. the supply of \c _s and the demand of
413    /// \c _t).
414    CapacityScaling( const Graph &_graph,
415                     const LowerMap &_lower,
416                     const CapacityMap &_capacity,
417                     const CostMap &_cost,
418                     Node _s, Node _t,
419                     Supply _flow_value ) :
420      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
421      supply(_graph), flow(_graph, 0), potential(_graph, 0),
422      res_graph(_graph, capacity, flow),
423      red_cost(res_graph, cost, potential), imbalance(_graph),
424#ifdef WITH_SCALING
425      delta(0), delta_filter(res_graph, delta),
426      dres_graph(res_graph, delta_filter),
427      dijkstra(dres_graph, red_cost), pred(dres_graph),
428      delta_deficit(imbalance, delta)
429#else //WITHOUT_CAPACITY_SCALING
430      dijkstra(res_graph, red_cost), pred(res_graph),
431      has_deficit(imbalance)
432#endif
433    {
434      // Removing nonzero lower bounds
435      capacity = subMap(_capacity, _lower);
436      for (NodeIt n(graph); n != INVALID; ++n) {
437        Supply s = 0;
438        if (n == _s) s =  _flow_value;
439        if (n == _t) s = -_flow_value;
440        for (InEdgeIt e(graph, n); e != INVALID; ++e)
441          s += _lower[e];
442        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
443          s -= _lower[e];
444        supply[n] = imbalance[n] = s;
445      }
446      valid_supply = true;
447    }
448
449    /// \brief Simple constructor of the class (without lower bounds).
450    ///
451    /// Simple constructor of the class (without lower bounds).
452    ///
453    /// \param _graph The directed graph the algorithm runs on.
454    /// \param _capacity The capacities (upper bounds) of the edges.
455    /// \param _cost The cost (length) values of the edges.
456    /// \param _s The source node.
457    /// \param _t The target node.
458    /// \param _flow_value The required amount of flow from node \c _s
459    /// to node \c _t (i.e. the supply of \c _s and the demand of
460    /// \c _t).
461    CapacityScaling( const Graph &_graph,
462                     const CapacityMap &_capacity,
463                     const CostMap &_cost,
464                     Node _s, Node _t,
465                     Supply _flow_value ) :
466      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
467      supply(_graph, 0), flow(_graph, 0), potential(_graph, 0),
468      res_graph(_graph, capacity, flow),
469      red_cost(res_graph, cost, potential), imbalance(_graph),
470#ifdef WITH_SCALING
471      delta(0), delta_filter(res_graph, delta),
472      dres_graph(res_graph, delta_filter),
473      dijkstra(dres_graph, red_cost), pred(dres_graph),
474      delta_deficit(imbalance, delta)
475#else //WITHOUT_CAPACITY_SCALING
476      dijkstra(res_graph, red_cost), pred(res_graph),
477      has_deficit(imbalance)
478#endif
479    {
480      supply[_s] =  _flow_value;
481      supply[_t] = -_flow_value;
482      valid_supply = true;
483    }
484
485    /// \brief Returns a const reference to the flow map.
486    ///
487    /// Returns a const reference to the flow map.
488    ///
489    /// \pre \ref run() must be called before using this function.
490    const FlowMap& flowMap() const {
491      return flow;
492    }
493
494    /// \brief Returns a const reference to the potential map (the dual
495    /// solution).
496    ///
497    /// Returns a const reference to the potential map (the dual
498    /// solution).
499    ///
500    /// \pre \ref run() must be called before using this function.
501    const PotentialMap& potentialMap() const {
502      return potential;
503    }
504
505    /// \brief Returns the total cost of the found flow.
506    ///
507    /// Returns the total cost of the found flow. The complexity of the
508    /// function is \f$ O(e) \f$.
509    ///
510    /// \pre \ref run() must be called before using this function.
511    Cost totalCost() const {
512      Cost c = 0;
513      for (EdgeIt e(graph); e != INVALID; ++e)
514        c += flow[e] * cost[e];
515      return c;
516    }
517
518    /// \brief Runs the algorithm.
519    ///
520    /// Runs the algorithm.
521    ///
522    /// \return \c true if a feasible flow can be found.
523    bool run() {
524      return init() && start();
525    }
526
527  protected:
528
529    /// \brief Initializes the algorithm.
530    bool init() {
531      if (!valid_supply) return false;
532
533      // Initalizing Dijkstra class
534      updater.potentialMap(potential);
535      dijkstra.distMap(updater).predMap(pred);
536
537#ifdef WITH_SCALING
538      // Initilaizing delta value
539      Supply max_sup = 0, max_dem = 0;
540      for (NodeIt n(graph); n != INVALID; ++n) {
541        if (supply[n] >  max_sup) max_sup =  supply[n];
542        if (supply[n] < -max_dem) max_dem = -supply[n];
543      }
544      if (max_dem < max_sup) max_sup = max_dem;
545      for (delta = 1; 2 * delta < max_sup; delta *= 2) ;
546#endif
547      return true;
548    }
549
550#ifdef WITH_SCALING
551    /// \brief Executes the capacity scaling version of the successive
552    /// shortest path algorithm.
553    bool start() {
554      typedef typename DeltaResGraph::EdgeIt DeltaResEdgeIt;
555      typedef typename DeltaResGraph::Edge DeltaResEdge;
556#ifdef _DEBUG_ITER_
557      int dijk_num = 0;
558#endif
559
560      // Processing capacity scaling phases
561      ResNode s, t;
562      for ( ; delta >= 1; delta = delta < 4 && delta > 1 ?
563                                  1 : delta / 4 )
564      {
565        // Saturating edges not satisfying the optimality condition
566        Capacity r;
567        for (DeltaResEdgeIt e(dres_graph); e != INVALID; ++e) {
568          if (red_cost[e] < 0) {
569            res_graph.augment(e, r = res_graph.rescap(e));
570            imbalance[dres_graph.target(e)] += r;
571            imbalance[dres_graph.source(e)] -= r;
572          }
573        }
574
575        // Finding excess nodes
576        excess_nodes.clear();
577        deficit_nodes.clear();
578        for (ResNodeIt n(res_graph); n != INVALID; ++n) {
579          if (imbalance[n] >=  delta) excess_nodes.push_back(n);
580          if (imbalance[n] <= -delta) deficit_nodes.push_back(n);
581        }
582        next_node = 0;
583
584        // Finding shortest paths
585        while (next_node < excess_nodes.size()) {
586          // Checking deficit nodes
587          if (delta > 1) {
588            bool delta_def = false;
589            for (int i = 0; i < deficit_nodes.size(); ++i) {
590              if (imbalance[deficit_nodes[i]] <= -delta) {
591                delta_def = true;
592                break;
593              }
594            }
595            if (!delta_def) break;
596          }
597
598          // Running Dijkstra
599          s = excess_nodes[next_node];
600          updater.init();
601          dijkstra.init();
602          dijkstra.addSource(s);
603#ifdef _DEBUG_ITER_
604          ++dijk_num;
605#endif
606          if ((t = dijkstra.start(delta_deficit)) == INVALID) {
607            if (delta > 1) {
608              ++next_node;
609              continue;
610            }
611            return false;
612          }
613
614          // Updating node potentials
615          updater.update();
616
617          // Augment along a shortest path from s to t
618          Capacity d = imbalance[s] < -imbalance[t] ?
619            imbalance[s] : -imbalance[t];
620          ResNode u = t;
621          ResEdge e;
622          if (d > delta) {
623            while ((e = pred[u]) != INVALID) {
624              if (res_graph.rescap(e) < d) d = res_graph.rescap(e);
625              u = dres_graph.source(e);
626            }
627          }
628          u = t;
629          while ((e = pred[u]) != INVALID) {
630            res_graph.augment(e, d);
631            u = dres_graph.source(e);
632          }
633          imbalance[s] -= d;
634          imbalance[t] += d;
635          if (imbalance[s] < delta) ++next_node;
636        }
637      }
638#ifdef _DEBUG_ITER_
639      std::cout << "Cost Scaling algorithm finished with running Dijkstra algorithm "
640        << dijk_num << " times." << std::endl;
641#endif
642
643      // Handling nonzero lower bounds
644      if (lower) {
645        for (EdgeIt e(graph); e != INVALID; ++e)
646          flow[e] += (*lower)[e];
647      }
648      return true;
649    }
650
651#else //WITHOUT_CAPACITY_SCALING
652    /// \brief Executes the successive shortest path algorithm without
653    /// capacity scaling.
654    bool start() {
655      // Finding excess nodes
656      for (ResNodeIt n(res_graph); n != INVALID; ++n) {
657        if (imbalance[n] > 0) excess_nodes.push_back(n);
658      }
659      if (excess_nodes.size() == 0) return true;
660      next_node = 0;
661
662      // Finding shortest paths
663      ResNode s, t;
664      while ( imbalance[excess_nodes[next_node]] > 0 ||
665              ++next_node < excess_nodes.size() )
666      {
667        // Running Dijkstra
668        s = excess_nodes[next_node];
669        updater.init();
670        dijkstra.init();
671        dijkstra.addSource(s);
672        if ((t = dijkstra.start(has_deficit)) == INVALID)
673          return false;
674
675        // Updating node potentials
676        updater.update();
677
678        // Augmenting along a shortest path from s to t
679        Capacity delta = imbalance[s] < -imbalance[t] ?
680          imbalance[s] : -imbalance[t];
681        ResNode u = t;
682        ResEdge e;
683        while ((e = pred[u]) != INVALID) {
684          if (res_graph.rescap(e) < delta) delta = res_graph.rescap(e);
685          u = res_graph.source(e);
686        }
687        u = t;
688        while ((e = pred[u]) != INVALID) {
689          res_graph.augment(e, delta);
690          u = res_graph.source(e);
691        }
692        imbalance[s] -= delta;
693        imbalance[t] += delta;
694      }
695
696      // Handling nonzero lower bounds
697      if (lower) {
698        for (EdgeIt e(graph); e != INVALID; ++e)
699          flow[e] += (*lower)[e];
700      }
701      return true;
702    }
703#endif
704
705  }; //class CapacityScaling
706
707  ///@}
708
709} //namespace lemon
710
711#endif //LEMON_CAPACITY_SCALING_H
Note: See TracBrowser for help on using the repository browser.