COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/cycle_canceling.h @ 2581:054566ac0934

Last change on this file since 2581:054566ac0934 was 2581:054566ac0934, checked in by Peter Kovacs, 16 years ago

Query improvements in the min cost flow algorithms.

  • External flow and potential maps can be used.
  • New query functions: flow() and potential().
  • CycleCanceling? also provides dual solution (node potentials).
  • Doc improvements.
File size: 17.8 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2008
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_CYCLE_CANCELING_H
20#define LEMON_CYCLE_CANCELING_H
21
22/// \ingroup min_cost_flow
23///
24/// \file
25/// \brief Cycle-canceling algorithm for finding a minimum cost flow.
26
27#include <vector>
28#include <lemon/graph_adaptor.h>
29#include <lemon/path.h>
30
31#include <lemon/circulation.h>
32#include <lemon/bellman_ford.h>
33#include <lemon/min_mean_cycle.h>
34
35namespace lemon {
36
37  /// \addtogroup min_cost_flow
38  /// @{
39
40  /// \brief Implementation of a cycle-canceling algorithm for
41  /// finding a minimum cost flow.
42  ///
43  /// \ref CycleCanceling implements a cycle-canceling algorithm for
44  /// finding a minimum cost flow.
45  ///
46  /// \tparam Graph The directed graph type the algorithm runs on.
47  /// \tparam LowerMap The type of the lower bound map.
48  /// \tparam CapacityMap The type of the capacity (upper bound) map.
49  /// \tparam CostMap The type of the cost (length) map.
50  /// \tparam SupplyMap The type of the supply map.
51  ///
52  /// \warning
53  /// - Edge capacities and costs should be \e non-negative \e integers.
54  /// - Supply values should be \e signed \e integers.
55  /// - The value types of the maps should be convertible to each other.
56  /// - \c CostMap::Value must be signed type.
57  ///
58  /// \note By default the \ref BellmanFord "Bellman-Ford" algorithm is
59  /// used for negative cycle detection with limited iteration number.
60  /// However \ref CycleCanceling also provides the "Minimum Mean
61  /// Cycle-Canceling" algorithm, which is \e strongly \e polynomial,
62  /// but rather slower in practice.
63  /// To use this version of the algorithm, call \ref run() with \c true
64  /// parameter.
65  ///
66  /// \author Peter Kovacs
67
68  template < typename Graph,
69             typename LowerMap = typename Graph::template EdgeMap<int>,
70             typename CapacityMap = typename Graph::template EdgeMap<int>,
71             typename CostMap = typename Graph::template EdgeMap<int>,
72             typename SupplyMap = typename Graph::template NodeMap<int> >
73  class CycleCanceling
74  {
75    GRAPH_TYPEDEFS(typename Graph);
76
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> CapacityEdgeMap;
81    typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
82
83    typedef ResGraphAdaptor< const Graph, Capacity,
84                             CapacityEdgeMap, CapacityEdgeMap > 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    /// The type of the flow map.
93    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
94    /// The type of the potential map.
95    typedef typename Graph::template NodeMap<Cost> PotentialMap;
96
97  private:
98
99    /// \brief Map adaptor class for handling residual edge costs.
100    ///
101    /// \ref ResidualCostMap is a map adaptor class for handling
102    /// residual edge costs.
103    class ResidualCostMap : public MapBase<ResEdge, Cost>
104    {
105    private:
106
107      const CostMap &_cost_map;
108
109    public:
110
111      ///\e
112      ResidualCostMap(const CostMap &cost_map) : _cost_map(cost_map) {}
113
114      ///\e
115      Cost operator[](const ResEdge &e) const {
116        return ResGraph::forward(e) ? _cost_map[e] : -_cost_map[e];
117      }
118
119    }; //class ResidualCostMap
120
121  private:
122
123    // The maximum number of iterations for the first execution of the
124    // Bellman-Ford algorithm. It should be at least 2.
125    static const int BF_FIRST_LIMIT = 2;
126    // The iteration limit for the Bellman-Ford algorithm is multiplied
127    // by BF_ALPHA in every round.
128    static const double BF_ALPHA = 1.5;
129
130  private:
131
132    // The directed graph the algorithm runs on
133    const Graph &_graph;
134    // The original lower bound map
135    const LowerMap *_lower;
136    // The modified capacity map
137    CapacityEdgeMap _capacity;
138    // The original cost map
139    const CostMap &_cost;
140    // The modified supply map
141    SupplyNodeMap _supply;
142    bool _valid_supply;
143
144    // Edge map of the current flow
145    FlowMap *_flow;
146    bool _local_flow;
147    // Node map of the current potentials
148    PotentialMap *_potential;
149    bool _local_potential;
150
151    // The residual graph
152    ResGraph *_res_graph;
153    // The residual cost map
154    ResidualCostMap _res_cost;
155
156  public:
157
158    /// \brief General constructor (with lower bounds).
159    ///
160    /// General constructor (with lower bounds).
161    ///
162    /// \param graph The directed graph the algorithm runs on.
163    /// \param lower The lower bounds of the edges.
164    /// \param capacity The capacities (upper bounds) of the edges.
165    /// \param cost The cost (length) values of the edges.
166    /// \param supply The supply values of the nodes (signed).
167    CycleCanceling( const Graph &graph,
168                    const LowerMap &lower,
169                    const CapacityMap &capacity,
170                    const CostMap &cost,
171                    const SupplyMap &supply ) :
172      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
173      _supply(graph), _flow(0), _local_flow(false),
174      _potential(0), _local_potential(false), _res_cost(_cost)
175    {
176      // Removing non-zero lower bounds
177      _capacity = subMap(capacity, lower);
178      Supply sum = 0;
179      for (NodeIt n(_graph); n != INVALID; ++n) {
180        Supply s = supply[n];
181        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
182          s += lower[e];
183        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
184          s -= lower[e];
185        sum += (_supply[n] = s);
186      }
187      _valid_supply = sum == 0;
188    }
189
190    /// \brief General constructor (without lower bounds).
191    ///
192    /// General constructor (without lower bounds).
193    ///
194    /// \param graph The directed graph the algorithm runs on.
195    /// \param capacity The capacities (upper bounds) of the edges.
196    /// \param cost The cost (length) values of the edges.
197    /// \param supply The supply values of the nodes (signed).
198    CycleCanceling( const Graph &graph,
199                    const CapacityMap &capacity,
200                    const CostMap &cost,
201                    const SupplyMap &supply ) :
202      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
203      _supply(supply), _flow(0), _local_flow(false),
204      _potential(0), _local_potential(false), _res_cost(_cost)
205    {
206      // Checking the sum of supply values
207      Supply sum = 0;
208      for (NodeIt n(_graph); n != INVALID; ++n) sum += _supply[n];
209      _valid_supply = sum == 0;
210    }
211
212    /// \brief Simple constructor (with lower bounds).
213    ///
214    /// Simple constructor (with lower bounds).
215    ///
216    /// \param graph The directed graph the algorithm runs on.
217    /// \param lower The lower bounds of the edges.
218    /// \param capacity The capacities (upper bounds) of the edges.
219    /// \param cost The cost (length) values of the edges.
220    /// \param s The source node.
221    /// \param t The target node.
222    /// \param flow_value The required amount of flow from node \c s
223    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
224    CycleCanceling( const Graph &graph,
225                    const LowerMap &lower,
226                    const CapacityMap &capacity,
227                    const CostMap &cost,
228                    Node s, Node t,
229                    Supply flow_value ) :
230      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
231      _supply(graph), _flow(0), _local_flow(false),
232      _potential(0), _local_potential(false), _res_cost(_cost)
233    {
234      // Removing non-zero lower bounds
235      _capacity = subMap(capacity, lower);
236      for (NodeIt n(_graph); n != INVALID; ++n) {
237        Supply sum = 0;
238        if (n == s) sum =  flow_value;
239        if (n == t) sum = -flow_value;
240        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
241          sum += lower[e];
242        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
243          sum -= lower[e];
244        _supply[n] = sum;
245      }
246      _valid_supply = true;
247    }
248
249    /// \brief Simple constructor (without lower bounds).
250    ///
251    /// Simple constructor (without lower bounds).
252    ///
253    /// \param graph The directed graph the algorithm runs on.
254    /// \param capacity The capacities (upper bounds) of the edges.
255    /// \param cost The cost (length) values of the edges.
256    /// \param s The source node.
257    /// \param t The target node.
258    /// \param flow_value The required amount of flow from node \c s
259    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
260    CycleCanceling( const Graph &graph,
261                    const CapacityMap &capacity,
262                    const CostMap &cost,
263                    Node s, Node t,
264                    Supply flow_value ) :
265      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
266      _supply(graph, 0), _flow(0), _local_flow(false),
267      _potential(0), _local_potential(false), _res_cost(_cost)
268    {
269      _supply[s] =  flow_value;
270      _supply[t] = -flow_value;
271      _valid_supply = true;
272    }
273
274    /// Destructor.
275    ~CycleCanceling() {
276      if (_local_flow) delete _flow;
277      if (_local_potential) delete _potential;
278      delete _res_graph;
279    }
280
281    /// \brief Sets the flow map.
282    ///
283    /// Sets the flow map.
284    ///
285    /// \return \c (*this)
286    CycleCanceling& flowMap(FlowMap &map) {
287      if (_local_flow) {
288        delete _flow;
289        _local_flow = false;
290      }
291      _flow = &map;
292      return *this;
293    }
294
295    /// \brief Sets the potential map.
296    ///
297    /// Sets the potential map.
298    ///
299    /// \return \c (*this)
300    CycleCanceling& potentialMap(PotentialMap &map) {
301      if (_local_potential) {
302        delete _potential;
303        _local_potential = false;
304      }
305      _potential = &map;
306      return *this;
307    }
308
309    /// \name Execution control
310    /// The only way to execute the algorithm is to call the run()
311    /// function.
312
313    /// @{
314
315    /// \brief Runs the algorithm.
316    ///
317    /// Runs the algorithm.
318    ///
319    /// \param min_mean_cc Set this parameter to \c true to run the
320    /// "Minimum Mean Cycle-Canceling" algorithm, which is strongly
321    /// polynomial, but rather slower in practice.
322    ///
323    /// \return \c true if a feasible flow can be found.
324    bool run(bool min_mean_cc = false) {
325      return init() && start(min_mean_cc);
326    }
327
328    /// @}
329
330    /// \name Query Functions
331    /// The result of the algorithm can be obtained using these
332    /// functions.
333    /// \n run() must be called before using them.
334
335    /// @{
336
337    /// \brief Returns a const reference to the edge map storing the
338    /// found flow.
339    ///
340    /// Returns a const reference to the edge map storing the found flow.
341    ///
342    /// \pre \ref run() must be called before using this function.
343    const FlowMap& flowMap() const {
344      return *_flow;
345    }
346
347    /// \brief Returns a const reference to the node map storing the
348    /// found potentials (the dual solution).
349    ///
350    /// Returns a const reference to the node map storing the found
351    /// potentials (the dual solution).
352    ///
353    /// \pre \ref run() must be called before using this function.
354    const PotentialMap& potentialMap() const {
355      return *_potential;
356    }
357
358    /// \brief Returns the flow on the edge.
359    ///
360    /// Returns the flow on the edge.
361    ///
362    /// \pre \ref run() must be called before using this function.
363    Capacity flow(const Edge& edge) const {
364      return (*_flow)[edge];
365    }
366
367    /// \brief Returns the potential of the node.
368    ///
369    /// Returns the potential of the node.
370    ///
371    /// \pre \ref run() must be called before using this function.
372    Cost potential(const Node& node) const {
373      return (*_potential)[node];
374    }
375
376    /// \brief Returns the total cost of the found flow.
377    ///
378    /// Returns the total cost of the found flow. The complexity of the
379    /// function is \f$ O(e) \f$.
380    ///
381    /// \pre \ref run() must be called before using this function.
382    Cost totalCost() const {
383      Cost c = 0;
384      for (EdgeIt e(_graph); e != INVALID; ++e)
385        c += (*_flow)[e] * _cost[e];
386      return c;
387    }
388
389    /// @}
390
391  private:
392
393    /// Initializes the algorithm.
394    bool init() {
395      if (!_valid_supply) return false;
396
397      // Initializing flow and potential maps
398      if (!_flow) {
399        _flow = new FlowMap(_graph);
400        _local_flow = true;
401      }
402      if (!_potential) {
403        _potential = new PotentialMap(_graph);
404        _local_potential = true;
405      }
406
407      _res_graph = new ResGraph(_graph, _capacity, *_flow);
408
409      // Finding a feasible flow using Circulation
410      Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
411                   SupplyMap >
412        circulation( _graph, constMap<Edge>(Capacity(0)), _capacity,
413                     _supply );
414      return circulation.flowMap(*_flow).run();
415    }
416
417    bool start(bool min_mean_cc) {
418      if (min_mean_cc)
419        startMinMean();
420      else
421        start();
422
423      // Handling non-zero lower bounds
424      if (_lower) {
425        for (EdgeIt e(_graph); e != INVALID; ++e)
426          (*_flow)[e] += (*_lower)[e];
427      }
428      return true;
429    }
430
431    /// \brief Executes the algorithm using \ref BellmanFord.
432    ///
433    /// Executes the algorithm using the \ref BellmanFord
434    /// "Bellman-Ford" algorithm for negative cycle detection with
435    /// successively larger limit for the number of iterations.
436    void start() {
437      typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(*_res_graph);
438      typename ResGraph::template NodeMap<int> visited(*_res_graph);
439      std::vector<ResEdge> cycle;
440      int node_num = countNodes(_graph);
441
442      int length_bound = BF_FIRST_LIMIT;
443      bool optimal = false;
444      while (!optimal) {
445        BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost);
446        bf.predMap(pred);
447        bf.init(0);
448        int iter_num = 0;
449        bool cycle_found = false;
450        while (!cycle_found) {
451          int curr_iter_num = iter_num + length_bound <= node_num ?
452                              length_bound : node_num - iter_num;
453          iter_num += curr_iter_num;
454          int real_iter_num = curr_iter_num;
455          for (int i = 0; i < curr_iter_num; ++i) {
456            if (bf.processNextWeakRound()) {
457              real_iter_num = i;
458              break;
459            }
460          }
461          if (real_iter_num < curr_iter_num) {
462            // Optimal flow is found
463            optimal = true;
464            // Setting node potentials
465            for (NodeIt n(_graph); n != INVALID; ++n)
466              (*_potential)[n] = bf.dist(n);
467            break;
468          } else {
469            // Searching for node disjoint negative cycles
470            for (ResNodeIt n(*_res_graph); n != INVALID; ++n)
471              visited[n] = 0;
472            int id = 0;
473            for (ResNodeIt n(*_res_graph); n != INVALID; ++n) {
474              if (visited[n] > 0) continue;
475              visited[n] = ++id;
476              ResNode u = pred[n] == INVALID ?
477                          INVALID : _res_graph->source(pred[n]);
478              while (u != INVALID && visited[u] == 0) {
479                visited[u] = id;
480                u = pred[u] == INVALID ?
481                    INVALID : _res_graph->source(pred[u]);
482              }
483              if (u != INVALID && visited[u] == id) {
484                // Finding the negative cycle
485                cycle_found = true;
486                cycle.clear();
487                ResEdge e = pred[u];
488                cycle.push_back(e);
489                Capacity d = _res_graph->rescap(e);
490                while (_res_graph->source(e) != u) {
491                  cycle.push_back(e = pred[_res_graph->source(e)]);
492                  if (_res_graph->rescap(e) < d)
493                    d = _res_graph->rescap(e);
494                }
495
496                // Augmenting along the cycle
497                for (int i = 0; i < int(cycle.size()); ++i)
498                  _res_graph->augment(cycle[i], d);
499              }
500            }
501          }
502
503          if (!cycle_found)
504            length_bound = int(length_bound * BF_ALPHA);
505        }
506      }
507    }
508
509    /// \brief Executes the algorithm using \ref MinMeanCycle.
510    ///
511    /// Executes the algorithm using \ref MinMeanCycle for negative
512    /// cycle detection.
513    void startMinMean() {
514      typedef Path<ResGraph> ResPath;
515      MinMeanCycle<ResGraph, ResidualCostMap> mmc(*_res_graph, _res_cost);
516      ResPath cycle;
517
518      mmc.cyclePath(cycle).init();
519      if (mmc.findMinMean()) {
520        while (mmc.cycleLength() < 0) {
521          // Finding the cycle
522          mmc.findCycle();
523
524          // Finding the largest flow amount that can be augmented
525          // along the cycle
526          Capacity delta = 0;
527          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
528            if (delta == 0 || _res_graph->rescap(e) < delta)
529              delta = _res_graph->rescap(e);
530          }
531
532          // Augmenting along the cycle
533          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
534            _res_graph->augment(e, delta);
535
536          // Finding the minimum cycle mean for the modified residual
537          // graph
538          mmc.reset();
539          if (!mmc.findMinMean()) break;
540        }
541      }
542
543      // Computing node potentials
544      BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost);
545      bf.init(0); bf.start();
546      for (NodeIt n(_graph); n != INVALID; ++n)
547        (*_potential)[n] = bf.dist(n);
548    }
549
550  }; //class CycleCanceling
551
552  ///@}
553
554} //namespace lemon
555
556#endif //LEMON_CYCLE_CANCELING_H
Note: See TracBrowser for help on using the repository browser.