COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/cycle_canceling.h @ 2623:90defb96ee61

Last change on this file since 2623:90defb96ee61 was 2623:90defb96ee61, checked in by Peter Kovacs, 11 years ago

Add missing pointer initializing in min cost flow classes

File size: 17.9 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  template < typename Graph,
68             typename LowerMap = typename Graph::template EdgeMap<int>,
69             typename CapacityMap = typename Graph::template EdgeMap<int>,
70             typename CostMap = typename Graph::template EdgeMap<int>,
71             typename SupplyMap = typename Graph::template NodeMap<int> >
72  class CycleCanceling
73  {
74    GRAPH_TYPEDEFS(typename Graph);
75
76    typedef typename CapacityMap::Value Capacity;
77    typedef typename CostMap::Value Cost;
78    typedef typename SupplyMap::Value Supply;
79    typedef typename Graph::template EdgeMap<Capacity> CapacityEdgeMap;
80    typedef typename Graph::template NodeMap<Supply> SupplyNodeMap;
81
82    typedef ResGraphAdaptor< const Graph, Capacity,
83                             CapacityEdgeMap, CapacityEdgeMap > ResGraph;
84    typedef typename ResGraph::Node ResNode;
85    typedef typename ResGraph::NodeIt ResNodeIt;
86    typedef typename ResGraph::Edge ResEdge;
87    typedef typename ResGraph::EdgeIt ResEdgeIt;
88
89  public:
90
91    /// The type of the flow map.
92    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
93    /// The type of the potential map.
94    typedef typename Graph::template NodeMap<Cost> PotentialMap;
95
96  private:
97
98    /// \brief Map adaptor class for handling residual edge costs.
99    ///
100    /// Map adaptor class for handling residual edge costs.
101    class ResidualCostMap : public MapBase<ResEdge, Cost>
102    {
103    private:
104
105      const CostMap &_cost_map;
106
107    public:
108
109      ///\e
110      ResidualCostMap(const CostMap &cost_map) : _cost_map(cost_map) {}
111
112      ///\e
113      Cost operator[](const ResEdge &e) const {
114        return ResGraph::forward(e) ? _cost_map[e] : -_cost_map[e];
115      }
116
117    }; //class ResidualCostMap
118
119  private:
120
121    // The maximum number of iterations for the first execution of the
122    // Bellman-Ford algorithm. It should be at least 2.
123    static const int BF_FIRST_LIMIT  = 2;
124    // The iteration limit for the Bellman-Ford algorithm is multiplied
125    // by BF_LIMIT_FACTOR/100 in every round.
126    static const int BF_LIMIT_FACTOR = 150;
127
128  private:
129
130    // The directed graph the algorithm runs on
131    const Graph &_graph;
132    // The original lower bound map
133    const LowerMap *_lower;
134    // The modified capacity map
135    CapacityEdgeMap _capacity;
136    // The original cost map
137    const CostMap &_cost;
138    // The modified supply map
139    SupplyNodeMap _supply;
140    bool _valid_supply;
141
142    // Edge map of the current flow
143    FlowMap *_flow;
144    bool _local_flow;
145    // Node map of the current potentials
146    PotentialMap *_potential;
147    bool _local_potential;
148
149    // The residual graph
150    ResGraph *_res_graph;
151    // The residual cost map
152    ResidualCostMap _res_cost;
153
154  public:
155
156    /// \brief General constructor (with lower bounds).
157    ///
158    /// General constructor (with lower bounds).
159    ///
160    /// \param graph The directed graph the algorithm runs on.
161    /// \param lower The lower bounds of the edges.
162    /// \param capacity The capacities (upper bounds) of the edges.
163    /// \param cost The cost (length) values of the edges.
164    /// \param supply The supply values of the nodes (signed).
165    CycleCanceling( const Graph &graph,
166                    const LowerMap &lower,
167                    const CapacityMap &capacity,
168                    const CostMap &cost,
169                    const SupplyMap &supply ) :
170      _graph(graph), _lower(&lower), _capacity(graph), _cost(cost),
171      _supply(graph), _flow(NULL), _local_flow(false),
172      _potential(NULL), _local_potential(false), _res_graph(NULL),
173      _res_cost(_cost)
174    {
175      // Removing non-zero lower bounds
176      _capacity = subMap(capacity, lower);
177      Supply sum = 0;
178      for (NodeIt n(_graph); n != INVALID; ++n) {
179        Supply s = supply[n];
180        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
181          s += lower[e];
182        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
183          s -= lower[e];
184        sum += (_supply[n] = s);
185      }
186      _valid_supply = sum == 0;
187    }
188
189    /// \brief General constructor (without lower bounds).
190    ///
191    /// General constructor (without lower bounds).
192    ///
193    /// \param graph The directed graph the algorithm runs on.
194    /// \param capacity The capacities (upper bounds) of the edges.
195    /// \param cost The cost (length) values of the edges.
196    /// \param supply The supply values of the nodes (signed).
197    CycleCanceling( const Graph &graph,
198                    const CapacityMap &capacity,
199                    const CostMap &cost,
200                    const SupplyMap &supply ) :
201      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
202      _supply(supply), _flow(NULL), _local_flow(false),
203      _potential(NULL), _local_potential(false), _res_graph(NULL),
204      _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(NULL), _local_flow(false),
232      _potential(NULL), _local_potential(false), _res_graph(NULL),
233      _res_cost(_cost)
234    {
235      // Removing non-zero lower bounds
236      _capacity = subMap(capacity, lower);
237      for (NodeIt n(_graph); n != INVALID; ++n) {
238        Supply sum = 0;
239        if (n == s) sum =  flow_value;
240        if (n == t) sum = -flow_value;
241        for (InEdgeIt e(_graph, n); e != INVALID; ++e)
242          sum += lower[e];
243        for (OutEdgeIt e(_graph, n); e != INVALID; ++e)
244          sum -= lower[e];
245        _supply[n] = sum;
246      }
247      _valid_supply = true;
248    }
249
250    /// \brief Simple constructor (without lower bounds).
251    ///
252    /// Simple constructor (without lower bounds).
253    ///
254    /// \param graph The directed graph the algorithm runs on.
255    /// \param capacity The capacities (upper bounds) of the edges.
256    /// \param cost The cost (length) values of the edges.
257    /// \param s The source node.
258    /// \param t The target node.
259    /// \param flow_value The required amount of flow from node \c s
260    /// to node \c t (i.e. the supply of \c s and the demand of \c t).
261    CycleCanceling( const Graph &graph,
262                    const CapacityMap &capacity,
263                    const CostMap &cost,
264                    Node s, Node t,
265                    Supply flow_value ) :
266      _graph(graph), _lower(NULL), _capacity(capacity), _cost(cost),
267      _supply(graph, 0), _flow(NULL), _local_flow(false),
268      _potential(NULL), _local_potential(false), _res_graph(NULL),
269      _res_cost(_cost)
270    {
271      _supply[s] =  flow_value;
272      _supply[t] = -flow_value;
273      _valid_supply = true;
274    }
275
276    /// Destructor.
277    ~CycleCanceling() {
278      if (_local_flow) delete _flow;
279      if (_local_potential) delete _potential;
280      delete _res_graph;
281    }
282
283    /// \brief Set the flow map.
284    ///
285    /// Set the flow map.
286    ///
287    /// \return \c (*this)
288    CycleCanceling& flowMap(FlowMap &map) {
289      if (_local_flow) {
290        delete _flow;
291        _local_flow = false;
292      }
293      _flow = &map;
294      return *this;
295    }
296
297    /// \brief Set the potential map.
298    ///
299    /// Set the potential map.
300    ///
301    /// \return \c (*this)
302    CycleCanceling& potentialMap(PotentialMap &map) {
303      if (_local_potential) {
304        delete _potential;
305        _local_potential = false;
306      }
307      _potential = &map;
308      return *this;
309    }
310
311    /// \name Execution control
312
313    /// @{
314
315    /// \brief Run the algorithm.
316    ///
317    /// Run 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.\n
333    /// \ref lemon::CycleCanceling::run() "run()" must be called before
334    /// using them.
335
336    /// @{
337
338    /// \brief Return a const reference to the edge map storing the
339    /// found flow.
340    ///
341    /// Return a const reference to the edge map storing the found flow.
342    ///
343    /// \pre \ref run() must be called before using this function.
344    const FlowMap& flowMap() const {
345      return *_flow;
346    }
347
348    /// \brief Return a const reference to the node map storing the
349    /// found potentials (the dual solution).
350    ///
351    /// Return a const reference to the node map storing the found
352    /// potentials (the dual solution).
353    ///
354    /// \pre \ref run() must be called before using this function.
355    const PotentialMap& potentialMap() const {
356      return *_potential;
357    }
358
359    /// \brief Return the flow on the given edge.
360    ///
361    /// Return the flow on the given edge.
362    ///
363    /// \pre \ref run() must be called before using this function.
364    Capacity flow(const Edge& edge) const {
365      return (*_flow)[edge];
366    }
367
368    /// \brief Return the potential of the given node.
369    ///
370    /// Return the potential of the given node.
371    ///
372    /// \pre \ref run() must be called before using this function.
373    Cost potential(const Node& node) const {
374      return (*_potential)[node];
375    }
376
377    /// \brief Return the total cost of the found flow.
378    ///
379    /// Return the total cost of the found flow. The complexity of the
380    /// function is \f$ O(e) \f$.
381    ///
382    /// \pre \ref run() must be called before using this function.
383    Cost totalCost() const {
384      Cost c = 0;
385      for (EdgeIt e(_graph); e != INVALID; ++e)
386        c += (*_flow)[e] * _cost[e];
387      return c;
388    }
389
390    /// @}
391
392  private:
393
394    /// Initialize the algorithm.
395    bool init() {
396      if (!_valid_supply) return false;
397
398      // Initializing flow and potential maps
399      if (!_flow) {
400        _flow = new FlowMap(_graph);
401        _local_flow = true;
402      }
403      if (!_potential) {
404        _potential = new PotentialMap(_graph);
405        _local_potential = true;
406      }
407
408      _res_graph = new ResGraph(_graph, _capacity, *_flow);
409
410      // Finding a feasible flow using Circulation
411      Circulation< Graph, ConstMap<Edge, Capacity>, CapacityEdgeMap,
412                   SupplyMap >
413        circulation( _graph, constMap<Edge>(Capacity(0)), _capacity,
414                     _supply );
415      return circulation.flowMap(*_flow).run();
416    }
417
418    bool start(bool min_mean_cc) {
419      if (min_mean_cc)
420        startMinMean();
421      else
422        start();
423
424      // Handling non-zero lower bounds
425      if (_lower) {
426        for (EdgeIt e(_graph); e != INVALID; ++e)
427          (*_flow)[e] += (*_lower)[e];
428      }
429      return true;
430    }
431
432    /// \brief Execute the algorithm using \ref BellmanFord.
433    ///
434    /// Execute the algorithm using the \ref BellmanFord
435    /// "Bellman-Ford" algorithm for negative cycle detection with
436    /// successively larger limit for the number of iterations.
437    void start() {
438      typename BellmanFord<ResGraph, ResidualCostMap>::PredMap pred(*_res_graph);
439      typename ResGraph::template NodeMap<int> visited(*_res_graph);
440      std::vector<ResEdge> cycle;
441      int node_num = countNodes(_graph);
442
443      int length_bound = BF_FIRST_LIMIT;
444      bool optimal = false;
445      while (!optimal) {
446        BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost);
447        bf.predMap(pred);
448        bf.init(0);
449        int iter_num = 0;
450        bool cycle_found = false;
451        while (!cycle_found) {
452          int curr_iter_num = iter_num + length_bound <= node_num ?
453                              length_bound : node_num - iter_num;
454          iter_num += curr_iter_num;
455          int real_iter_num = curr_iter_num;
456          for (int i = 0; i < curr_iter_num; ++i) {
457            if (bf.processNextWeakRound()) {
458              real_iter_num = i;
459              break;
460            }
461          }
462          if (real_iter_num < curr_iter_num) {
463            // Optimal flow is found
464            optimal = true;
465            // Setting node potentials
466            for (NodeIt n(_graph); n != INVALID; ++n)
467              (*_potential)[n] = bf.dist(n);
468            break;
469          } else {
470            // Searching for node disjoint negative cycles
471            for (ResNodeIt n(*_res_graph); n != INVALID; ++n)
472              visited[n] = 0;
473            int id = 0;
474            for (ResNodeIt n(*_res_graph); n != INVALID; ++n) {
475              if (visited[n] > 0) continue;
476              visited[n] = ++id;
477              ResNode u = pred[n] == INVALID ?
478                          INVALID : _res_graph->source(pred[n]);
479              while (u != INVALID && visited[u] == 0) {
480                visited[u] = id;
481                u = pred[u] == INVALID ?
482                    INVALID : _res_graph->source(pred[u]);
483              }
484              if (u != INVALID && visited[u] == id) {
485                // Finding the negative cycle
486                cycle_found = true;
487                cycle.clear();
488                ResEdge e = pred[u];
489                cycle.push_back(e);
490                Capacity d = _res_graph->rescap(e);
491                while (_res_graph->source(e) != u) {
492                  cycle.push_back(e = pred[_res_graph->source(e)]);
493                  if (_res_graph->rescap(e) < d)
494                    d = _res_graph->rescap(e);
495                }
496
497                // Augmenting along the cycle
498                for (int i = 0; i < int(cycle.size()); ++i)
499                  _res_graph->augment(cycle[i], d);
500              }
501            }
502          }
503
504          if (!cycle_found)
505            length_bound = length_bound * BF_LIMIT_FACTOR / 100;
506        }
507      }
508    }
509
510    /// \brief Execute the algorithm using \ref MinMeanCycle.
511    ///
512    /// Execute the algorithm using \ref MinMeanCycle for negative
513    /// cycle detection.
514    void startMinMean() {
515      typedef Path<ResGraph> ResPath;
516      MinMeanCycle<ResGraph, ResidualCostMap> mmc(*_res_graph, _res_cost);
517      ResPath cycle;
518
519      mmc.cyclePath(cycle).init();
520      if (mmc.findMinMean()) {
521        while (mmc.cycleLength() < 0) {
522          // Finding the cycle
523          mmc.findCycle();
524
525          // Finding the largest flow amount that can be augmented
526          // along the cycle
527          Capacity delta = 0;
528          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
529            if (delta == 0 || _res_graph->rescap(e) < delta)
530              delta = _res_graph->rescap(e);
531          }
532
533          // Augmenting along the cycle
534          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
535            _res_graph->augment(e, delta);
536
537          // Finding the minimum cycle mean for the modified residual
538          // graph
539          mmc.reset();
540          if (!mmc.findMinMean()) break;
541        }
542      }
543
544      // Computing node potentials
545      BellmanFord<ResGraph, ResidualCostMap> bf(*_res_graph, _res_cost);
546      bf.init(0); bf.start();
547      for (NodeIt n(_graph); n != INVALID; ++n)
548        (*_potential)[n] = bf.dist(n);
549    }
550
551  }; //class CycleCanceling
552
553  ///@}
554
555} //namespace lemon
556
557#endif //LEMON_CYCLE_CANCELING_H
Note: See TracBrowser for help on using the repository browser.