COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/capacity_scaling.h @ 2440:c9218405595b

Last change on this file since 2440:c9218405595b was 2440:c9218405595b, checked in by Balazs Dezso, 13 years ago

Various min cost flow solvers

Patch from Peter Kovacs

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