COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/cycle_canceling.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: 15.2 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_CYCLE_CANCELING_H
20#define LEMON_CYCLE_CANCELING_H
21
22/// \ingroup min_cost_flow
23///
24/// \file
25/// \brief A cycle canceling algorithm for finding a minimum cost flow.
26
27#include <vector>
28#include <lemon/circulation.h>
29#include <lemon/graph_adaptor.h>
30
31/// \brief The used cycle canceling method.
32#define LIMITED_CYCLE_CANCELING
33//#define MIN_MEAN_CYCLE_CANCELING
34
35#ifdef LIMITED_CYCLE_CANCELING
36  #include <lemon/bellman_ford.h>
37  /// \brief The maximum number of iterations for the first execution
38  /// of the \ref lemon::BellmanFord "Bellman-Ford" algorithm.
39  #define STARTING_LIMIT        2
40  /// \brief The iteration limit for the
41  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
42  /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
43  #define ALPHA_MUL             3
44  /// \brief The iteration limit for the
45  /// \ref lemon::BellmanFord "Bellman-Ford" algorithm is multiplied by
46  /// <tt>ALPHA_MUL % ALPHA_DIV</tt> in every round.
47  #define ALPHA_DIV             2
48
49//#define _ONLY_ONE_CYCLE_
50//#define _DEBUG_ITER_
51#endif
52
53#ifdef MIN_MEAN_CYCLE_CANCELING
54  #include <lemon/min_mean_cycle.h>
55  #include <lemon/path.h>
56#endif
57
58namespace lemon {
59
60  /// \addtogroup min_cost_flow
61  /// @{
62
63  /// \brief Implementation of a cycle canceling algorithm for finding
64  /// a minimum cost flow.
65  ///
66  /// \ref lemon::CycleCanceling "CycleCanceling" implements a cycle
67  /// canceling algorithm for finding a minimum cost flow.
68  ///
69  /// \param Graph The directed graph type the algorithm runs on.
70  /// \param LowerMap The type of the lower bound map.
71  /// \param CapacityMap The type of the capacity (upper bound) map.
72  /// \param CostMap The type of the cost (length) map.
73  /// \param SupplyMap The type of the supply map.
74  ///
75  /// \warning
76  /// - Edge capacities and costs should be nonnegative integers.
77  ///   However \c CostMap::Value should be signed type.
78  /// - Supply values should be integers.
79  /// - \c LowerMap::Value must be convertible to
80  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
81  ///   convertible to \c SupplyMap::Value.
82  ///
83  /// \author Peter Kovacs
84
85template < typename Graph,
86           typename LowerMap = typename Graph::template EdgeMap<int>,
87           typename CapacityMap = LowerMap,
88           typename CostMap = typename Graph::template EdgeMap<int>,
89           typename SupplyMap = typename Graph::template NodeMap
90                                <typename CapacityMap::Value> >
91  class CycleCanceling
92  {
93    typedef typename Graph::Node Node;
94    typedef typename Graph::NodeIt NodeIt;
95    typedef typename Graph::Edge Edge;
96    typedef typename Graph::EdgeIt EdgeIt;
97    typedef typename Graph::InEdgeIt InEdgeIt;
98    typedef typename Graph::OutEdgeIt OutEdgeIt;
99
100    typedef typename LowerMap::Value Lower;
101    typedef typename CapacityMap::Value Capacity;
102    typedef typename CostMap::Value Cost;
103    typedef typename SupplyMap::Value Supply;
104    typedef typename Graph::template EdgeMap<Capacity> CapacityRefMap;
105    typedef typename Graph::template NodeMap<Supply> SupplyRefMap;
106
107    typedef ResGraphAdaptor< const Graph, Capacity,
108                             CapacityRefMap, CapacityRefMap > ResGraph;
109    typedef typename ResGraph::Node ResNode;
110    typedef typename ResGraph::NodeIt ResNodeIt;
111    typedef typename ResGraph::Edge ResEdge;
112    typedef typename ResGraph::EdgeIt ResEdgeIt;
113
114  public:
115
116    /// \brief The type of the flow map.
117    typedef CapacityRefMap FlowMap;
118
119  protected:
120
121    /// \brief Map adaptor class for demand map.
122    class DemandMap : public MapBase<Node, Supply>
123    {
124    private:
125
126      const SupplyMap *map;
127
128    public:
129
130      typedef typename MapBase<Node, Supply>::Value Value;
131      typedef typename MapBase<Node, Supply>::Key Key;
132
133      DemandMap(const SupplyMap &_map) : map(&_map) {}
134
135      Value operator[](const Key &e) const {
136        return -(*map)[e];
137      }
138
139    }; //class DemandMap
140
141    /// \brief Map adaptor class for handling residual edge costs.
142    class ResCostMap : public MapBase<ResEdge, Cost>
143    {
144    private:
145
146      const CostMap &cost_map;
147
148    public:
149
150      typedef typename MapBase<ResEdge, Cost>::Value Value;
151      typedef typename MapBase<ResEdge, Cost>::Key Key;
152
153      ResCostMap(const CostMap &_cost) : cost_map(_cost) {}
154
155      Value operator[](const Key &e) const {
156        return ResGraph::forward(e) ? cost_map[e] : -cost_map[e];
157      }
158
159    }; //class ResCostMap
160
161  protected:
162
163    /// \brief The directed graph the algorithm runs on.
164    const Graph &graph;
165    /// \brief The original lower bound map.
166    const LowerMap *lower;
167    /// \brief The modified capacity map.
168    CapacityRefMap capacity;
169    /// \brief The cost map.
170    const CostMap &cost;
171    /// \brief The modified supply map.
172    SupplyRefMap supply;
173    /// \brief The modified demand map.
174    DemandMap demand;
175    /// \brief The sum of supply values equals zero.
176    bool valid_supply;
177
178    /// \brief The current flow.
179    FlowMap flow;
180    /// \brief The residual graph.
181    ResGraph res_graph;
182    /// \brief The residual cost map.
183    ResCostMap res_cost;
184
185  public :
186
187    /// \brief General constructor of the class (with lower bounds).
188    ///
189    /// General constructor of the class (with lower bounds).
190    ///
191    /// \param _graph The directed graph the algorithm runs on.
192    /// \param _lower The lower bounds of the edges.
193    /// \param _capacity The capacities (upper bounds) of the edges.
194    /// \param _cost The cost (length) values of the edges.
195    /// \param _supply The supply values of the nodes (signed).
196    CycleCanceling( const Graph &_graph,
197                    const LowerMap &_lower,
198                    const CapacityMap &_capacity,
199                    const CostMap &_cost,
200                    const SupplyMap &_supply ) :
201      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
202      supply(_graph), demand(supply), flow(_graph, 0),
203      res_graph(_graph, capacity, flow), res_cost(cost)
204    {
205      // Removing nonzero lower bounds
206      capacity = subMap(_capacity, _lower);
207      Supply sum = 0;
208      for (NodeIt n(graph); n != INVALID; ++n) {
209        Supply s = _supply[n];
210        for (InEdgeIt e(graph, n); e != INVALID; ++e)
211          s += _lower[e];
212        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
213          s -= _lower[e];
214        sum += (supply[n] = s);
215      }
216      valid_supply = sum == 0;
217    }
218
219    /// \brief General constructor of the class (without lower bounds).
220    ///
221    /// General constructor of the class (without lower bounds).
222    ///
223    /// \param _graph The directed graph the algorithm runs on.
224    /// \param _capacity The capacities (upper bounds) of the edges.
225    /// \param _cost The cost (length) values of the edges.
226    /// \param _supply The supply values of the nodes (signed).
227    CycleCanceling( const Graph &_graph,
228                    const CapacityMap &_capacity,
229                    const CostMap &_cost,
230                    const SupplyMap &_supply ) :
231      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
232      supply(_supply), demand(supply), flow(_graph, 0),
233      res_graph(_graph, capacity, flow), res_cost(cost)
234    {
235      // Checking the sum of supply values
236      Supply sum = 0;
237      for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
238      valid_supply = sum == 0;
239    }
240
241
242    /// \brief Simple constructor of the class (with lower bounds).
243    ///
244    /// Simple constructor of the class (with lower bounds).
245    ///
246    /// \param _graph The directed graph the algorithm runs on.
247    /// \param _lower The lower bounds of the edges.
248    /// \param _capacity The capacities (upper bounds) of the edges.
249    /// \param _cost The cost (length) values of the edges.
250    /// \param _s The source node.
251    /// \param _t The target node.
252    /// \param _flow_value The required amount of flow from node \c _s
253    /// to node \c _t (i.e. the supply of \c _s and the demand of
254    /// \c _t).
255    CycleCanceling( const Graph &_graph,
256                    const LowerMap &_lower,
257                    const CapacityMap &_capacity,
258                    const CostMap &_cost,
259                    Node _s, Node _t,
260                    Supply _flow_value ) :
261      graph(_graph), lower(&_lower), capacity(_graph), cost(_cost),
262      supply(_graph), demand(supply), flow(_graph, 0),
263      res_graph(_graph, capacity, flow), res_cost(cost)
264    {
265      // Removing nonzero lower bounds
266      capacity = subMap(_capacity, _lower);
267      for (NodeIt n(graph); n != INVALID; ++n) {
268        Supply s = 0;
269        if (n == _s) s =  _flow_value;
270        if (n == _t) s = -_flow_value;
271        for (InEdgeIt e(graph, n); e != INVALID; ++e)
272          s += _lower[e];
273        for (OutEdgeIt e(graph, n); e != INVALID; ++e)
274          s -= _lower[e];
275        supply[n] = s;
276      }
277      valid_supply = true;
278    }
279
280    /// \brief Simple constructor of the class (without lower bounds).
281    ///
282    /// Simple constructor of the class (without lower bounds).
283    ///
284    /// \param _graph The directed graph the algorithm runs on.
285    /// \param _capacity The capacities (upper bounds) of the edges.
286    /// \param _cost The cost (length) values of the edges.
287    /// \param _s The source node.
288    /// \param _t The target node.
289    /// \param _flow_value The required amount of flow from node \c _s
290    /// to node \c _t (i.e. the supply of \c _s and the demand of
291    /// \c _t).
292    CycleCanceling( const Graph &_graph,
293                    const CapacityMap &_capacity,
294                    const CostMap &_cost,
295                    Node _s, Node _t,
296                    Supply _flow_value ) :
297      graph(_graph), lower(NULL), capacity(_capacity), cost(_cost),
298      supply(_graph, 0), demand(supply), flow(_graph, 0),
299      res_graph(_graph, capacity, flow), res_cost(cost)
300    {
301      supply[_s] =  _flow_value;
302      supply[_t] = -_flow_value;
303      valid_supply = true;
304    }
305
306    /// \brief Returns a const reference to the flow map.
307    ///
308    /// Returns a const reference to the flow map.
309    ///
310    /// \pre \ref run() must be called before using this function.
311    const FlowMap& flowMap() const {
312      return flow;
313    }
314
315    /// \brief Returns the total cost of the found flow.
316    ///
317    /// Returns the total cost of the found flow. The complexity of the
318    /// function is \f$ O(e) \f$.
319    ///
320    /// \pre \ref run() must be called before using this function.
321    Cost totalCost() const {
322      Cost c = 0;
323      for (EdgeIt e(graph); e != INVALID; ++e)
324        c += flow[e] * cost[e];
325      return c;
326    }
327
328    /// \brief Runs the algorithm.
329    ///
330    /// Runs the algorithm.
331    ///
332    /// \return \c true if a feasible flow can be found.
333    bool run() {
334      return init() && start();
335    }
336
337  protected:
338
339    /// \brief Initializes the algorithm.
340    bool init() {
341      // Checking the sum of supply values
342      Supply sum = 0;
343      for (NodeIt n(graph); n != INVALID; ++n) sum += supply[n];
344      if (sum != 0) return false;
345
346      // Finding a feasible flow
347      Circulation< Graph, Capacity, FlowMap, ConstMap<Edge, Capacity>,
348                   CapacityRefMap, DemandMap >
349        circulation( graph, constMap<Edge>((Capacity)0),
350                     capacity, demand, flow );
351      return circulation.run() == -1;
352    }
353
354#ifdef LIMITED_CYCLE_CANCELING
355    /// \brief Executes a cycle canceling algorithm using
356    /// \ref lemon::BellmanFord "Bellman-Ford" algorithm with limited
357    /// iteration count.
358    bool start() {
359      typename BellmanFord<ResGraph, ResCostMap>::PredMap pred(res_graph);
360      typename ResGraph::template NodeMap<int> visited(res_graph);
361      std::vector<ResEdge> cycle;
362      int node_num = countNodes(graph);
363
364#ifdef _DEBUG_ITER_
365      int cycle_num = 0;
366#endif
367      int length_bound = STARTING_LIMIT;
368      bool optimal = false;
369      while (!optimal) {
370        BellmanFord<ResGraph, ResCostMap> bf(res_graph, res_cost);
371        bf.predMap(pred);
372        bf.init(0);
373        int iter_num = 0;
374        bool cycle_found = false;
375        while (!cycle_found) {
376          int curr_iter_num = iter_num + length_bound <= node_num ?
377                              length_bound : node_num - iter_num;
378          iter_num += curr_iter_num;
379          int real_iter_num = curr_iter_num;
380          for (int i = 0; i < curr_iter_num; ++i) {
381            if (bf.processNextWeakRound()) {
382              real_iter_num = i;
383              break;
384            }
385          }
386          if (real_iter_num < curr_iter_num) {
387            optimal = true;
388            break;
389          } else {
390            // Searching for node disjoint negative cycles
391            for (ResNodeIt n(res_graph); n != INVALID; ++n)
392              visited[n] = 0;
393            int id = 0;
394            for (ResNodeIt n(res_graph); n != INVALID; ++n) {
395              if (visited[n] > 0) continue;
396              visited[n] = ++id;
397              ResNode u = pred[n] == INVALID ?
398                          INVALID : res_graph.source(pred[n]);
399              while (u != INVALID && visited[u] == 0) {
400                visited[u] = id;
401                u = pred[u] == INVALID ?
402                    INVALID : res_graph.source(pred[u]);
403              }
404              if (u != INVALID && visited[u] == id) {
405                // Finding the negative cycle
406                cycle_found = true;
407                cycle.clear();
408                ResEdge e = pred[u];
409                cycle.push_back(e);
410                Capacity d = res_graph.rescap(e);
411                while (res_graph.source(e) != u) {
412                  cycle.push_back(e = pred[res_graph.source(e)]);
413                  if (res_graph.rescap(e) < d)
414                    d = res_graph.rescap(e);
415                }
416#ifdef _DEBUG_ITER_
417                ++cycle_num;
418#endif
419                // Augmenting along the cycle
420                for (int i = 0; i < cycle.size(); ++i)
421                  res_graph.augment(cycle[i], d);
422#ifdef _ONLY_ONE_CYCLE_
423                break;
424#endif
425              }
426            }
427          }
428
429          if (!cycle_found)
430            length_bound = length_bound * ALPHA_MUL / ALPHA_DIV;
431        }
432      }
433
434#ifdef _DEBUG_ITER_
435      std::cout << "Limited cycle canceling algorithm finished. "
436                << "Found " << cycle_num << " negative cycles."
437                << std::endl;
438#endif
439
440      // Handling nonzero lower bounds
441      if (lower) {
442        for (EdgeIt e(graph); e != INVALID; ++e)
443          flow[e] += (*lower)[e];
444      }
445      return true;
446    }
447#endif
448
449#ifdef MIN_MEAN_CYCLE_CANCELING
450    /// \brief Executes the minimum mean cycle canceling algorithm
451    /// using \ref lemon::MinMeanCycle "MinMeanCycle" class.
452    bool start() {
453      typedef Path<ResGraph> ResPath;
454      MinMeanCycle<ResGraph, ResCostMap> mmc(res_graph, res_cost);
455      ResPath cycle;
456
457#ifdef _DEBUG_ITER_
458      int cycle_num = 0;
459#endif
460      mmc.cyclePath(cycle).init();
461      if (mmc.findMinMean()) {
462        while (mmc.cycleLength() < 0) {
463#ifdef _DEBUG_ITER_
464          ++iter;
465#endif
466          // Finding the cycle
467          mmc.findCycle();
468
469          // Finding the largest flow amount that can be augmented
470          // along the cycle
471          Capacity delta = 0;
472          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e) {
473            if (delta == 0 || res_graph.rescap(e) < delta)
474              delta = res_graph.rescap(e);
475          }
476
477          // Augmenting along the cycle
478          for (typename ResPath::EdgeIt e(cycle); e != INVALID; ++e)
479            res_graph.augment(e, delta);
480
481          // Finding the minimum cycle mean for the modified residual
482          // graph
483          mmc.reset();
484          if (!mmc.findMinMean()) break;
485        }
486      }
487
488#ifdef _DEBUG_ITER_
489      std::cout << "Minimum mean cycle canceling algorithm finished. "
490                << "Found " << cycle_num << " negative cycles."
491                << std::endl;
492#endif
493
494      // Handling nonzero lower bounds
495      if (lower) {
496        for (EdgeIt e(graph); e != INVALID; ++e)
497          flow[e] += (*lower)[e];
498      }
499      return true;
500    }
501#endif
502
503  }; //class CycleCanceling
504
505  ///@}
506
507} //namespace lemon
508
509#endif //LEMON_CYCLE_CANCELING_H
Note: See TracBrowser for help on using the repository browser.