COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/cycle_canceling.h @ 2556:74c2c81055e1

Last change on this file since 2556:74c2c81055e1 was 2556:74c2c81055e1, checked in by Peter Kovacs, 12 years ago

Cleanup in the minimum cost flow files.
The changes only affects the documentation and the look of the source codes.

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