COIN-OR::LEMON - Graph Library

source: lemon/lemon/edmonds_karp.h @ 1300:62dba6c90f35

Last change on this file since 1300:62dba6c90f35 was 1270:dceba191c00d, checked in by Alpar Juttner <alpar@…>, 11 years ago

Apply unify-sources.sh to the source tree

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