COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/cycle_canceling.h @ 2544:5143b01bf1d5

Last change on this file since 2544:5143b01bf1d5 was 2544:5143b01bf1d5, checked in by Peter Kovacs, 12 years ago

Bug fix (Circulation interface changed).

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