1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
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.
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
19 #ifndef LEMON_EDMONDS_KARP_H
20 #define LEMON_EDMONDS_KARP_H
24 /// \brief Implementation of the Edmonds-Karp algorithm.
26 #include <lemon/tolerance.h>
31 /// \brief Default traits class of EdmondsKarp class.
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 {
39 /// \brief The digraph type the algorithm runs on.
42 /// \brief The type of the map that stores the arc capacities.
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;
48 /// \brief The type of the flow values.
49 typedef typename CapacityMap::Value Value;
51 /// \brief The type of the map that stores the flow values.
53 /// The type of the map that stores the flow values.
54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
56 typedef GR::ArcMap<Value> FlowMap;
58 typedef typename Digraph::template ArcMap<Value> FlowMap;
61 /// \brief Instantiates a FlowMap.
63 /// This function instantiates a \ref FlowMap.
64 /// \param digraph The digraph for which we would like to define
66 static FlowMap* createFlowMap(const Digraph& digraph) {
67 return new FlowMap(digraph);
70 /// \brief The tolerance used by the algorithm
72 /// The tolerance used by the algorithm to handle inexact computation.
73 typedef lemon::Tolerance<Value> Tolerance;
79 /// \brief Edmonds-Karp algorithms class.
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.
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.
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.
106 template <typename GR, typename CAP, typename TR>
108 template <typename GR,
109 typename CAP = typename GR::template ArcMap<int>,
110 typename TR = EdmondsKarpDefaultTraits<GR, CAP> >
115 /// The \ref EdmondsKarpDefaultTraits "traits class" of the algorithm.
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;
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;
131 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
132 typedef typename Digraph::template NodeMap<Arc> PredMap;
134 const Digraph& _graph;
135 const CapacityMap* _capacity;
137 Node _source, _target;
143 std::vector<Node> _queue;
145 Tolerance _tolerance;
148 void createStructures() {
150 _flow = Traits::createFlowMap(_graph);
154 _pred = new PredMap(_graph);
156 _queue.resize(countNodes(_graph));
159 void destroyStructures() {
170 ///\name Named template parameters
174 template <typename T>
175 struct DefFlowMapTraits : public Traits {
177 static FlowMap *createFlowMap(const Digraph&) {
178 LEMON_ASSERT(false, "FlowMap is not initialized");
183 /// \brief \ref named-templ-param "Named parameter" for setting
186 /// \ref named-templ-param "Named parameter" for setting FlowMap
188 template <typename T>
190 : public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > {
191 typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
203 /// \brief The constructor of the class.
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()
215 LEMON_ASSERT(_source != _target,
216 "Flow source and target are the same nodes.");
219 /// \brief Destructor.
226 /// \brief Sets the capacity map.
228 /// Sets the capacity map.
229 /// \return <tt>(*this)</tt>
230 EdmondsKarp& capacityMap(const CapacityMap& map) {
235 /// \brief Sets the flow map.
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,
242 /// \return <tt>(*this)</tt>
243 EdmondsKarp& flowMap(FlowMap& map) {
252 /// \brief Sets the source node.
254 /// Sets the source node.
255 /// \return <tt>(*this)</tt>
256 EdmondsKarp& source(const Node& node) {
261 /// \brief Sets the target node.
263 /// Sets the target node.
264 /// \return <tt>(*this)</tt>
265 EdmondsKarp& target(const Node& node) {
270 /// \brief Sets the tolerance used by algorithm.
272 /// Sets the tolerance used by algorithm.
273 /// \return <tt>(*this)</tt>
274 EdmondsKarp& tolerance(const Tolerance& tolerance) {
275 _tolerance = tolerance;
279 /// \brief Returns a const reference to the tolerance.
281 /// Returns a const reference to the tolerance object used by
283 const Tolerance& tolerance() const {
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.
295 /// \brief Initializes the algorithm.
297 /// Initializes the internal data structures and sets the initial
298 /// flow to zero on each arc.
301 for (ArcIt it(_graph); it != INVALID; ++it) {
307 /// \brief Initializes the algorithm using the given flow map.
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
314 template <typename FlowMap>
315 void flowInit(const FlowMap& flowMap) {
317 for (ArcIt e(_graph); e != INVALID; ++e) {
318 _flow->set(e, flowMap[e]);
321 for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
322 _flow_value += (*_flow)[jt];
324 for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
325 _flow_value -= (*_flow)[jt];
329 /// \brief Initializes the algorithm using the given flow map.
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
336 /// \return \c false when the given \c flowMap does not contain a
338 template <typename FlowMap>
339 bool checkedFlowInit(const FlowMap& flowMap) {
341 for (ArcIt e(_graph); e != INVALID; ++e) {
342 _flow->set(e, flowMap[e]);
344 for (NodeIt it(_graph); it != INVALID; ++it) {
345 if (it == _source || it == _target) continue;
347 for (OutArcIt jt(_graph, it); jt != INVALID; ++jt) {
348 outFlow += (*_flow)[jt];
351 for (InArcIt jt(_graph, it); jt != INVALID; ++jt) {
352 inFlow += (*_flow)[jt];
354 if (_tolerance.different(outFlow, inFlow)) {
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;
363 for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
364 _flow_value += (*_flow)[jt];
366 for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
367 _flow_value -= (*_flow)[jt];
372 /// \brief Augments the solution along a shortest path.
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
380 /// \return \c false when the augmenting did not success, i.e. the
381 /// current flow is a feasible and optimal solution.
383 for (NodeIt n(_graph); n != INVALID; ++n) {
384 _pred->set(n, INVALID);
387 int first = 0, last = 1;
390 _pred->set(_source, OutArcIt(_graph, _source));
392 while (first != last && (*_pred)[_target] == INVALID) {
393 Node n = _queue[first++];
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) {
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) {
413 if ((*_pred)[_target] != INVALID) {
417 Value prem = (*_capacity)[e] - (*_flow)[e];
418 n = _graph.source(e);
419 while (n != _source) {
421 if (_graph.target(e) == n) {
422 Value rem = (*_capacity)[e] - (*_flow)[e];
423 if (rem < prem) prem = rem;
424 n = _graph.source(e);
426 Value rem = (*_flow)[e];
427 if (rem < prem) prem = rem;
428 n = _graph.target(e);
435 _flow->set(e, (*_flow)[e] + prem);
436 n = _graph.source(e);
437 while (n != _source) {
439 if (_graph.target(e) == n) {
440 _flow->set(e, (*_flow)[e] + prem);
441 n = _graph.source(e);
443 _flow->set(e, (*_flow)[e] - prem);
444 n = _graph.target(e);
455 /// \brief Executes the algorithm
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.
465 /// \brief Runs the algorithm.
467 /// Runs the Edmonds-Karp algorithm.
468 /// \note ek.run() is just a shortcut of the following code.
480 /// \name Query Functions
481 /// The result of the Edmonds-Karp algorithm can be obtained using these
483 /// Either \ref run() or \ref start() should be called before using them.
487 /// \brief Returns the value of the maximum flow.
489 /// Returns the value of the maximum flow found by the algorithm.
491 /// \pre Either \ref run() or \ref init() must be called before
492 /// using this function.
493 Value flowValue() const {
497 /// \brief Returns the flow value on the given arc.
499 /// Returns the flow value on the given arc.
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];
507 /// \brief Returns a const reference to the flow map.
509 /// Returns a const reference to the arc map storing the found flow.
511 /// \pre Either \ref run() or \ref init() must be called before
512 /// using this function.
513 const FlowMap& flowMap() const {
517 /// \brief Returns \c true when the node is on the source side of the
520 /// Returns true when the node is on the source side of the found
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;
529 /// \brief Gives back a minimum value cut.
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.
535 /// \note This function calls \ref minCut() for each node, so it runs in
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);
545 cutMap.set(_source, true);