COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/edmonds_karp.h @ 2034:b71f8ff62046

Last change on this file since 2034:b71f8ff62046 was 2034:b71f8ff62046, checked in by Balazs Dezso, 18 years ago

Edmonds-Karp MaxFlow?
ResGraphAdaptor? with Tolerance

File size: 11.6 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
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 flowalgs
24/// \brief Implementation of the Edmonds-Karp algorithm.
25
26#include <lemon/graph_adaptor.h>
27#include <lemon/tolerance.h>
28#include <lemon/bfs.h>
29
30namespace lemon {
31
32  /// \ingroup flowalgs
33  /// \brief Edmonds-Karp algorithms class.
34  ///
35  /// This class provides an implementation of the \e Edmonds-Karp \e
36  /// algorithm producing a flow of maximum value in a directed
37  /// graph. The Edmonds-Karp algorithm is slower than the Preflow algorithm
38  /// but it has an advantage of the step-by-step execution control with
39  /// feasible flow solutions. The \e source node, the \e target node, the \e
40  /// capacity of the edges and the \e starting \e flow value of the
41  /// edges should be passed to the algorithm through the
42  /// constructor. It is possible to change these quantities using the
43  /// functions \ref source, \ref target, \ref capacityMap and \ref
44  /// flowMap.
45  ///
46  /// The time complexity of the algorithm is O(n * e^2) in worst case.
47  /// Always try the preflow algorithm instead of this if you does not
48  /// have some additional reason than to compute the optimal flow which
49  /// has O(n^3) time complexity.
50  ///
51  /// \param _Graph The directed graph type the algorithm runs on.
52  /// \param _Number The number type of the capacities and the flow values.
53  /// \param _CapacityMap The capacity map type.
54  /// \param _FlowMap The flow map type.
55  /// \param _Tolerance The tolerance class to handle computation problems.
56  ///
57  /// \author Balazs Dezso
58  template <typename _Graph, typename _Number,
59            typename _CapacityMap = typename _Graph::template EdgeMap<_Number>,
60            typename _FlowMap = typename _Graph::template EdgeMap<_Number>,
61            typename _Tolerance = Tolerance<_Number> >
62  class EdmondsKarp {
63  public:
64
65    /// \brief \ref Exception for the case when the source equals the target.
66    ///
67    /// \ref Exception for the case when the source equals the target.
68    ///
69    class InvalidArgument : public lemon::LogicError {
70    public:
71      virtual const char* exceptionName() const {
72        return "lemon::EdmondsKarp::InvalidArgument";
73      }
74    };
75
76
77    /// \brief The graph type the algorithm runs on.
78    typedef _Graph Graph;
79    /// \brief The value type of the algorithms.
80    typedef _Number Number;
81    /// \brief The capacity map on the edges.
82    typedef _CapacityMap CapacityMap;
83    /// \brief The flow map on the edges.
84    typedef _FlowMap FlowMap;
85    /// \brief The tolerance used by the algorithm.
86    typedef _Tolerance Tolerance;
87
88    typedef ResGraphAdaptor<Graph, Number, CapacityMap,
89                            FlowMap, Tolerance> ResGraph;
90
91  private:
92
93    typedef typename Graph::Node Node;
94    typedef typename Graph::Edge Edge;
95   
96    typedef typename Graph::NodeIt NodeIt;
97    typedef typename Graph::EdgeIt EdgeIt;
98    typedef typename Graph::InEdgeIt InEdgeIt;
99    typedef typename Graph::OutEdgeIt OutEdgeIt;
100   
101  public:
102
103    /// \brief The constructor of the class.
104    ///
105    /// The constructor of the class.
106    /// \param _graph The directed graph the algorithm runs on.
107    /// \param _source The source node.
108    /// \param _target The target node.
109    /// \param _capacity The capacity of the edges.
110    /// \param _flow The flow of the edges.
111    /// \param _tolerance Tolerance class.
112    /// Except the graph, all of these parameters can be reset by
113    /// calling \ref source, \ref target, \ref capacityMap and \ref
114    /// flowMap, resp.
115    EdmondsKarp(const Graph& graph, Node source, Node target,
116                const CapacityMap& capacity, FlowMap& flow,
117                const Tolerance& tolerance = Tolerance())
118      : _graph(graph), _capacity(capacity), _flow(flow),
119        _tolerance(tolerance), _resgraph(graph, capacity, flow, tolerance),
120        _source(source), _target(target)
121    {
122      if (_source == _target) {
123        throw InvalidArgument();
124      }
125    }
126
127    /// \brief Initializes the algorithm
128    ///
129    /// It sets the flow to empty flow.
130    void init() {
131      for (EdgeIt it(_graph); it != INVALID; ++it) {
132        _flow.set(it, 0);
133      }
134      _value = 0;
135    }
136   
137    /// \brief Initializes the algorithm
138    ///
139    /// If the flow map initially flow this let the flow map
140    /// unchanged but the flow value will be set by the flow
141    /// on the outedges from the source.
142    void flowInit() {
143      _value = 0;
144      for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
145        _value += _flow[jt];
146      }
147      for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
148        _value -= _flow[jt];
149      }
150    }
151
152    /// \brief Initializes the algorithm
153    ///
154    /// If the flow map initially flow this let the flow map
155    /// unchanged but the flow value will be set by the flow
156    /// on the outedges from the source. It also checks that
157    /// the flow map really contains a flow.
158    /// \return %True when the flow map really a flow.
159    bool checkedFlowInit() {
160      _value = 0;
161      for (OutEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
162        _value += _flow[jt];
163      }
164      for (InEdgeIt jt(_graph, _source); jt != INVALID; ++jt) {
165        _value -= _flow[jt];
166      }
167      for (NodeIt it(_graph); it != INVALID; ++it) {
168        if (it == _source || it == _target) continue;
169        Number outFlow = 0;
170        for (OutEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
171          outFlow += _flow[jt];
172        }
173        Number inFlow = 0;
174        for (InEdgeIt jt(_graph, it); jt != INVALID; ++jt) {
175          inFlow += _flow[jt];
176        }
177        if (_tolerance.different(outFlow, inFlow)) {
178          return false;
179        }
180      }
181      for (EdgeIt it(_graph); it != INVALID; ++it) {
182        if (_tolerance.less(_flow[it], 0)) return false;
183        if (_tolerance.less(_capacity[it], _flow[it])) return false;
184      }
185      return true;
186    }
187
188    /// \brief Augment the solution on an edge shortest path.
189    ///
190    /// Augment the solution on an edge shortest path. It search an
191    /// edge shortest path between the source and the target
192    /// in the residual graph with the bfs algoritm.
193    /// Then it increase the flow on this path with the minimal residual
194    /// capacity on the path. If there is not such path it gives back
195    /// false.
196    /// \return %False when the augmenting is not success so the
197    /// current flow is a feasible and optimal solution.
198    bool augment() {
199      typename Bfs<ResGraph>
200      ::template DefDistMap<NullMap<Node, int> >
201      ::Create bfs(_resgraph);
202
203      NullMap<Node, int> distMap;
204      bfs.distMap(distMap);
205     
206      bfs.init();
207      bfs.addSource(_source);
208      bfs.start(_target);
209
210      if (!bfs.reached(_target)) {
211        return false;
212      }
213      Number min = _resgraph.rescap(bfs.predEdge(_target));
214      for (Node it = bfs.predNode(_target); it != _source;
215           it = bfs.predNode(it)) {
216        if (min > _resgraph.rescap(bfs.predEdge(it))) {
217          min = _resgraph.rescap(bfs.predEdge(it));
218        }
219      }
220      for (Node it = _target; it != _source; it = bfs.predNode(it)) {
221        _resgraph.augment(bfs.predEdge(it), min);
222      }
223      _value += min;
224      return true;
225    }
226
227    /// \brief Executes the algorithm
228    ///
229    /// It runs augmenting phases until the optimal solution is reached.
230    void start() {
231      while (augment()) {}
232    }
233
234    /// \brief Gives back the current flow value.
235    ///
236    /// Gives back the current flow _value.
237    Number flowValue() const {
238      return _value;
239    }
240
241    /// \brief runs the algorithm.
242    ///
243    /// It is just a shorthand for:
244    /// \code
245    /// ek.init();
246    /// ek.start();
247    /// \endcode
248    void run() {
249      init();
250      start();
251    }
252
253    /// \brief Returns a minimum value cut.
254    ///
255    /// Sets \c cut to the characteristic vector of a minimum value cut
256    /// It simply calls the minMinCut member.
257    template <typename CutMap>
258    void minCut(CutMap& cut) const {
259      minMinCut(cut);
260    }
261
262    /// \brief Returns the inclusionwise minimum of the minimum value cuts.
263    ///
264    /// Sets \c cut to the characteristic vector of the minimum value cut
265    /// which is inclusionwise minimum. It is computed by processing a
266    /// bfs from the source node \c source in the residual graph. 
267    template <typename CutMap>
268    void minMinCut(CutMap& cut) const {
269
270      typename Bfs<ResGraph>
271      ::template DefDistMap<NullMap<Node, int> >
272      ::template DefProcessedMap<CutMap>
273      ::Create bfs(_resgraph);
274
275      NullMap<Node, int> distMap;
276      bfs.distMap(distMap);
277
278      bfs.processedMap(cut);
279     
280      bfs.run(_source);
281    }
282
283    /// \brief Returns the inclusionwise minimum of the minimum value cuts.
284    ///
285    /// Sets \c cut to the characteristic vector of the minimum value cut
286    /// which is inclusionwise minimum. It is computed by processing a
287    /// bfs from the source node \c source in the residual graph. 
288    template <typename CutMap>
289    void maxMinCut(CutMap& cut) const {
290
291      typedef RevGraphAdaptor<const ResGraph> RevGraph;
292
293      RevGraph revgraph(_resgraph);
294
295      typename Bfs<RevGraph>
296      ::template DefDistMap<NullMap<Node, int> >
297      ::template DefPredMap<NullMap<Node, Edge> >
298      ::template DefProcessedMap<NotWriteMap<CutMap> >
299      ::Create bfs(revgraph);
300
301      NullMap<Node, int> distMap;
302      bfs.distMap(distMap);
303
304      NullMap<Node, Edge> predMap;
305      bfs.predMap(predMap);
306
307      NotWriteMap<CutMap> notcut(cut);
308      bfs.processedMap(notcut);
309     
310      bfs.run(_target);
311    }
312
313    /// \brief Sets the source node to \c _source.
314    ///
315    /// Sets the source node to \c _source.
316    void source(Node source) {
317      _source = source;
318    }
319
320    /// \brief Returns the source node.
321    ///
322    /// Returns the source node.
323    ///
324    Node source() const {
325      return _source;
326    }
327
328    /// \brief Sets the target node to \c target.
329    ///
330    /// Sets the target node to \c target.
331    void target(Node target) {
332      _target = target;
333    }
334
335    /// \brief Returns the target node.
336    ///
337    /// Returns the target node.
338    ///
339    Node target() const {
340      return _target;
341    }
342
343    /// \brief Sets the edge map of the capacities to _cap.
344    ///
345    /// Sets the edge map of the capacities to _cap.
346    ///
347    void capacityMap(const CapacityMap& capacity) {
348      _capacity = &capacity;
349    }
350
351    /// \brief Returns a reference to capacity map.
352    ///
353    /// Returns a reference to capacity map.
354    ///
355    const CapacityMap &capacityMap() const {
356      return *_capacity;
357    }
358
359    /// \brief Sets the edge map of the flows to \c flow.
360    ///
361    /// Sets the edge map of the flows to \c flow.
362    ///
363    void flowMap(FlowMap& flow) {
364      _flow = &flow;
365    }
366     
367    /// \brief Returns a reference to flow map.
368    ///
369    /// Returns a reference to flow map.
370    ///
371    const FlowMap &flowMap() const {
372      return *_flow;
373    }
374
375  private:
376   
377    const Graph& _graph;
378    const CapacityMap& _capacity;
379    FlowMap& _flow;
380    Tolerance _tolerance;
381   
382    ResGraph _resgraph;
383    Node _source, _target;
384    Number _value;
385   
386  };
387
388}
389
390#endif
Note: See TracBrowser for help on using the repository browser.