COIN-OR::LEMON - Graph Library

source: lemon/lemon/edmonds_karp.h @ 1225:6a8a688eacf6

Last change on this file since 1225:6a8a688eacf6 was 1225:6a8a688eacf6, checked in by Peter Kovacs <kpeter@…>, 7 years ago

Improve and fix API doc of EdmondsKarp? according to Preflow (#177)

File size: 16.0 KB
Line 
1/* -*- mode: C++; indent-tabs-mode: nil; -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library.
4 *
5 * Copyright (C) 2003-2010
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_EDMONDS_KARP_H
20#define LEMON_EDMONDS_KARP_H
21
22/// \file
23/// \ingroup max_flow
24/// \brief Implementation of the Edmonds-Karp algorithm.
25
26#include <lemon/tolerance.h>
27#include <vector>
28
29namespace lemon {
30
31  /// \brief Default traits class of EdmondsKarp class.
32  ///
33  /// Default traits class of EdmondsKarp class.
34  /// \param GR Digraph type.
35  /// \param CAP Type of capacity map.
36  template <typename GR, typename CAP>
37  struct EdmondsKarpDefaultTraits {
38
39    /// \brief The digraph type the algorithm runs on.
40    typedef GR Digraph;
41
42    /// \brief The type of the map that stores the arc capacities.
43    ///
44    /// The type of the map that stores the arc capacities.
45    /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
46    typedef CAP CapacityMap;
47
48    /// \brief The type of the flow values.
49    typedef typename CapacityMap::Value Value;
50
51    /// \brief The type of the map that stores the flow values.
52    ///
53    /// The type of the map that stores the flow values.
54    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
55#ifdef DOXYGEN
56    typedef GR::ArcMap<Value> FlowMap;
57#else
58    typedef typename Digraph::template ArcMap<Value> FlowMap;
59#endif
60
61    /// \brief Instantiates a FlowMap.
62    ///
63    /// This function instantiates a \ref FlowMap.
64    /// \param digraph The digraph for which we would like to define
65    /// the flow map.
66    static FlowMap* createFlowMap(const Digraph& digraph) {
67      return new FlowMap(digraph);
68    }
69
70    /// \brief The tolerance used by the algorithm
71    ///
72    /// The tolerance used by the algorithm to handle inexact computation.
73    typedef lemon::Tolerance<Value> Tolerance;
74
75  };
76
77  /// \ingroup max_flow
78  ///
79  /// \brief Edmonds-Karp algorithms class.
80  ///
81  /// This class provides an implementation of the \e Edmonds-Karp \e
82  /// algorithm producing a \ref max_flow "flow of maximum value" in a
83  /// digraph \ref clrs01algorithms, \ref amo93networkflows,
84  /// \ref edmondskarp72theoretical.
85  /// The Edmonds-Karp algorithm is slower than the Preflow
86  /// algorithm, but it has an advantage of the step-by-step execution
87  /// control with feasible flow solutions. The \e source node, the \e
88  /// target node, the \e capacity of the arcs and the \e starting \e
89  /// flow value of the arcs should be passed to the algorithm
90  /// through the constructor.
91  ///
92  /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
93  /// worst case. Always try the Preflow algorithm instead of this if
94  /// you just want to compute the optimal flow.
95  ///
96  /// \tparam GR The type of the digraph the algorithm runs on.
97  /// \tparam CAP The type of the capacity map. The default map
98  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
99  /// \tparam TR The traits class that defines various types used by the
100  /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits
101  /// "EdmondsKarpDefaultTraits<GR, CAP>".
102  /// In most cases, this parameter should not be set directly,
103  /// consider to use the named template parameters instead.
104
105#ifdef DOXYGEN
106  template <typename GR, typename CAP, typename TR>
107#else
108  template <typename GR,
109            typename CAP = typename GR::template ArcMap<int>,
110            typename TR = EdmondsKarpDefaultTraits<GR, CAP> >
111#endif
112  class EdmondsKarp {
113  public:
114
115    /// The \ref EdmondsKarpDefaultTraits "traits class" of the algorithm.
116    typedef TR Traits;
117    /// The type of the digraph the algorithm runs on.
118    typedef typename Traits::Digraph Digraph;
119    /// The type of the capacity map.
120    typedef typename Traits::CapacityMap CapacityMap;
121    /// The type of the flow values.
122    typedef typename Traits::Value Value;
123
124    /// The type of the flow map.
125    typedef typename Traits::FlowMap FlowMap;
126    /// The type of the tolerance.
127    typedef typename Traits::Tolerance Tolerance;
128
129  private:
130
131    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
132    typedef typename Digraph::template NodeMap<Arc> PredMap;
133   
134    const Digraph& _graph;
135    const CapacityMap* _capacity;
136
137    Node _source, _target;
138
139    FlowMap* _flow;
140    bool _local_flow;
141
142    PredMap* _pred;
143    std::vector<Node> _queue;
144   
145    Tolerance _tolerance;
146    Value _flow_value;
147
148    void createStructures() {
149      if (!_flow) {
150        _flow = Traits::createFlowMap(_graph);
151        _local_flow = true;
152      }
153      if (!_pred) {
154        _pred = new PredMap(_graph);
155      }
156      _queue.resize(countNodes(_graph));
157    }
158
159    void destroyStructures() {
160      if (_local_flow) {
161        delete _flow;
162      }
163      if (_pred) {
164        delete _pred;
165      }
166    }
167   
168  public:
169
170    ///\name Named template parameters
171
172    ///@{
173
174    template <typename T>
175    struct DefFlowMapTraits : public Traits {
176      typedef T FlowMap;
177      static FlowMap *createFlowMap(const Digraph&) {
178        LEMON_ASSERT(false, "FlowMap is not initialized");
179        return 0;
180      }
181    };
182
183    /// \brief \ref named-templ-param "Named parameter" for setting
184    /// FlowMap type
185    ///
186    /// \ref named-templ-param "Named parameter" for setting FlowMap
187    /// type
188    template <typename T>
189    struct DefFlowMap
190      : public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > {
191      typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
192      Create;
193    };
194
195    /// @}
196
197  protected:
198   
199    EdmondsKarp() {}
200
201  public:
202
203    /// \brief The constructor of the class.
204    ///
205    /// The constructor of the class.
206    /// \param digraph The digraph the algorithm runs on.
207    /// \param capacity The capacity of the arcs.
208    /// \param source The source node.
209    /// \param target The target node.
210    EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity,
211                Node source, Node target)
212      : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
213        _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
214    {
215      LEMON_ASSERT(_source != _target,
216                   "Flow source and target are the same nodes.");
217    }
218
219    /// \brief Destructor.
220    ///
221    /// Destructor.
222    ~EdmondsKarp() {
223      destroyStructures();
224    }
225
226    /// \brief Sets the capacity map.
227    ///
228    /// Sets the capacity map.
229    /// \return <tt>(*this)</tt>
230    EdmondsKarp& capacityMap(const CapacityMap& map) {
231      _capacity = &map;
232      return *this;
233    }
234
235    /// \brief Sets the flow map.
236    ///
237    /// Sets the flow map.
238    /// If you don't use this function before calling \ref run() or
239    /// \ref init(), an instance will be allocated automatically.
240    /// The destructor deallocates this automatically allocated map,
241    /// of course.
242    /// \return <tt>(*this)</tt>
243    EdmondsKarp& flowMap(FlowMap& map) {
244      if (_local_flow) {
245        delete _flow;
246        _local_flow = false;
247      }
248      _flow = &map;
249      return *this;
250    }
251
252    /// \brief Sets the source node.
253    ///
254    /// Sets the source node.
255    /// \return <tt>(*this)</tt>
256    EdmondsKarp& source(const Node& node) {
257      _source = node;
258      return *this;
259    }
260
261    /// \brief Sets the target node.
262    ///
263    /// Sets the target node.
264    /// \return <tt>(*this)</tt>
265    EdmondsKarp& target(const Node& node) {
266      _target = node;
267      return *this;
268    }
269
270    /// \brief Sets the tolerance used by algorithm.
271    ///
272    /// Sets the tolerance used by algorithm.
273    /// \return <tt>(*this)</tt>
274    EdmondsKarp& tolerance(const Tolerance& tolerance) {
275      _tolerance = tolerance;
276      return *this;
277    }
278
279    /// \brief Returns a const reference to the tolerance.
280    ///
281    /// Returns a const reference to the tolerance object used by
282    /// the algorithm.
283    const Tolerance& tolerance() const {
284      return _tolerance;
285    }
286
287    /// \name Execution control
288    /// The simplest way to execute the algorithm is to use \ref run().\n
289    /// If you need better control on the initial solution or the execution,
290    /// you have to call one of the \ref init() functions first, then
291    /// \ref start() or multiple times the \ref augment() function.
292   
293    ///@{
294
295    /// \brief Initializes the algorithm.
296    ///
297    /// Initializes the internal data structures and sets the initial
298    /// flow to zero on each arc.
299    void init() {
300      createStructures();
301      for (ArcIt it(_graph); it != INVALID; ++it) {
302        _flow->set(it, 0);
303      }
304      _flow_value = 0;
305    }
306   
307    /// \brief Initializes the algorithm using the given flow map.
308    ///
309    /// Initializes the internal data structures and sets the initial
310    /// flow to the given \c flowMap. The \c flowMap should
311    /// contain a feasible flow, i.e. at each node excluding the source
312    /// and the target, the incoming flow should be equal to the
313    /// outgoing flow.
314    template <typename FlowMap>
315    void flowInit(const FlowMap& flowMap) {
316      createStructures();
317      for (ArcIt e(_graph); e != INVALID; ++e) {
318        _flow->set(e, flowMap[e]);
319      }
320      _flow_value = 0;
321      for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
322        _flow_value += (*_flow)[jt];
323      }
324      for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
325        _flow_value -= (*_flow)[jt];
326      }
327    }
328
329    /// \brief Initializes the algorithm using the given flow map.
330    ///
331    /// Initializes the internal data structures and sets the initial
332    /// flow to the given \c flowMap. The \c flowMap should
333    /// contain a feasible flow, i.e. at each node excluding the source
334    /// and the target, the incoming flow should be equal to the
335    /// outgoing flow.
336    /// \return \c false when the given \c flowMap does not contain a
337    /// feasible flow.
338    template <typename FlowMap>
339    bool checkedFlowInit(const FlowMap& flowMap) {
340      createStructures();
341      for (ArcIt e(_graph); e != INVALID; ++e) {
342        _flow->set(e, flowMap[e]);
343      }
344      for (NodeIt it(_graph); it != INVALID; ++it) {
345        if (it == _source || it == _target) continue;
346        Value outFlow = 0;
347        for (OutArcIt jt(_graph, it); jt != INVALID; ++jt) {
348          outFlow += (*_flow)[jt];
349        }
350        Value inFlow = 0;
351        for (InArcIt jt(_graph, it); jt != INVALID; ++jt) {
352          inFlow += (*_flow)[jt];
353        }
354        if (_tolerance.different(outFlow, inFlow)) {
355          return false;
356        }
357      }
358      for (ArcIt it(_graph); it != INVALID; ++it) {
359        if (_tolerance.less((*_flow)[it], 0)) return false;
360        if (_tolerance.less((*_capacity)[it], (*_flow)[it])) return false;
361      }
362      _flow_value = 0;
363      for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
364        _flow_value += (*_flow)[jt];
365      }
366      for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
367        _flow_value -= (*_flow)[jt];
368      }
369      return true;
370    }
371
372    /// \brief Augments the solution along a shortest path.
373    ///
374    /// Augments the solution along a shortest path. This function searches a
375    /// shortest path between the source and the target
376    /// in the residual digraph by the Bfs algoritm.
377    /// Then it increases the flow on this path with the minimal residual
378    /// capacity on the path. If there is no such path, it gives back
379    /// false.
380    /// \return \c false when the augmenting did not success, i.e. the
381    /// current flow is a feasible and optimal solution.
382    bool augment() {
383      for (NodeIt n(_graph); n != INVALID; ++n) {
384        _pred->set(n, INVALID);
385      }
386     
387      int first = 0, last = 1;
388     
389      _queue[0] = _source;
390      _pred->set(_source, OutArcIt(_graph, _source));
391
392      while (first != last && (*_pred)[_target] == INVALID) {
393        Node n = _queue[first++];
394       
395        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
396          Value rem = (*_capacity)[e] - (*_flow)[e];
397          Node t = _graph.target(e);
398          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
399            _pred->set(t, e);
400            _queue[last++] = t;
401          }
402        }
403        for (InArcIt e(_graph, n); e != INVALID; ++e) {
404          Value rem = (*_flow)[e];
405          Node t = _graph.source(e);
406          if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
407            _pred->set(t, e);
408            _queue[last++] = t;
409          }
410        }
411      }
412
413      if ((*_pred)[_target] != INVALID) {
414        Node n = _target;
415        Arc e = (*_pred)[n];
416
417        Value prem = (*_capacity)[e] - (*_flow)[e];
418        n = _graph.source(e);
419        while (n != _source) {
420          e = (*_pred)[n];
421          if (_graph.target(e) == n) {
422            Value rem = (*_capacity)[e] - (*_flow)[e];
423            if (rem < prem) prem = rem;
424            n = _graph.source(e);
425          } else {
426            Value rem = (*_flow)[e];
427            if (rem < prem) prem = rem;
428            n = _graph.target(e);   
429          }
430        }
431
432        n = _target;
433        e = (*_pred)[n];
434
435        _flow->set(e, (*_flow)[e] + prem);
436        n = _graph.source(e);
437        while (n != _source) {
438          e = (*_pred)[n];
439          if (_graph.target(e) == n) {
440            _flow->set(e, (*_flow)[e] + prem);
441            n = _graph.source(e);
442          } else {
443            _flow->set(e, (*_flow)[e] - prem);
444            n = _graph.target(e);   
445          }
446        }
447
448        _flow_value += prem;   
449        return true;
450      } else {
451        return false;
452      }
453    }
454
455    /// \brief Executes the algorithm
456    ///
457    /// Executes the algorithm by performing augmenting phases until the
458    /// optimal solution is reached.
459    /// \pre One of the \ref init() functions must be called before
460    /// using this function.
461    void start() {
462      while (augment()) {}
463    }
464
465    /// \brief Runs the algorithm.
466    ///
467    /// Runs the Edmonds-Karp algorithm.
468    /// \note ek.run() is just a shortcut of the following code.
469    ///\code
470    /// ek.init();
471    /// ek.start();
472    ///\endcode
473    void run() {
474      init();
475      start();
476    }
477
478    /// @}
479
480    /// \name Query Functions
481    /// The result of the Edmonds-Karp algorithm can be obtained using these
482    /// functions.\n
483    /// Either \ref run() or \ref start() should be called before using them.
484   
485    ///@{
486
487    /// \brief Returns the value of the maximum flow.
488    ///
489    /// Returns the value of the maximum flow found by the algorithm.
490    ///
491    /// \pre Either \ref run() or \ref init() must be called before
492    /// using this function.
493    Value flowValue() const {
494      return _flow_value;
495    }
496
497    /// \brief Returns the flow value on the given arc.
498    ///
499    /// Returns the flow value on the given arc.
500    ///
501    /// \pre Either \ref run() or \ref init() must be called before
502    /// using this function.
503    Value flow(const Arc& arc) const {
504      return (*_flow)[arc];
505    }
506
507    /// \brief Returns a const reference to the flow map.
508    ///
509    /// Returns a const reference to the arc map storing the found flow.
510    ///
511    /// \pre Either \ref run() or \ref init() must be called before
512    /// using this function.
513    const FlowMap& flowMap() const {
514      return *_flow;
515    }
516
517    /// \brief Returns \c true when the node is on the source side of the
518    /// minimum cut.
519    ///
520    /// Returns true when the node is on the source side of the found
521    /// minimum cut.
522    ///
523    /// \pre Either \ref run() or \ref init() must be called before
524    /// using this function.
525    bool minCut(const Node& node) const {
526      return ((*_pred)[node] != INVALID) or node == _source;
527    }
528
529    /// \brief Gives back a minimum value cut.
530    ///
531    /// Sets \c cutMap to the characteristic vector of a minimum value
532    /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
533    /// node map with \c bool (or convertible) value type.
534    ///
535    /// \note This function calls \ref minCut() for each node, so it runs in
536    /// O(n) time.
537    ///
538    /// \pre Either \ref run() or \ref init() must be called before
539    /// using this function.
540    template <typename CutMap>
541    void minCutMap(CutMap& cutMap) const {
542      for (NodeIt n(_graph); n != INVALID; ++n) {
543        cutMap.set(n, (*_pred)[n] != INVALID);
544      }
545      cutMap.set(_source, true);
546    }   
547
548    /// @}
549
550  };
551
552}
553
554#endif
Note: See TracBrowser for help on using the repository browser.