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 SetFlowMapTraits : 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, SetFlowMapTraits<T> > {
191 typedef EdmondsKarp<Digraph, CapacityMap, SetFlowMapTraits<T> > Create;
202 /// \brief The constructor of the class.
204 /// The constructor of the class.
205 /// \param digraph The digraph the algorithm runs on.
206 /// \param capacity The capacity of the arcs.
207 /// \param source The source node.
208 /// \param target The target node.
209 EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity,
210 Node source, Node target)
211 : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
212 _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
214 LEMON_ASSERT(_source != _target,
215 "Flow source and target are the same nodes.");
218 /// \brief Destructor.
225 /// \brief Sets the capacity map.
227 /// Sets the capacity map.
228 /// \return <tt>(*this)</tt>
229 EdmondsKarp& capacityMap(const CapacityMap& map) {
234 /// \brief Sets the flow map.
236 /// Sets the flow map.
237 /// If you don't use this function before calling \ref run() or
238 /// \ref init(), an instance will be allocated automatically.
239 /// The destructor deallocates this automatically allocated map,
241 /// \return <tt>(*this)</tt>
242 EdmondsKarp& flowMap(FlowMap& map) {
251 /// \brief Sets the source node.
253 /// Sets the source node.
254 /// \return <tt>(*this)</tt>
255 EdmondsKarp& source(const Node& node) {
260 /// \brief Sets the target node.
262 /// Sets the target node.
263 /// \return <tt>(*this)</tt>
264 EdmondsKarp& target(const Node& node) {
269 /// \brief Sets the tolerance used by algorithm.
271 /// Sets the tolerance used by algorithm.
272 /// \return <tt>(*this)</tt>
273 EdmondsKarp& tolerance(const Tolerance& tolerance) {
274 _tolerance = tolerance;
278 /// \brief Returns a const reference to the tolerance.
280 /// Returns a const reference to the tolerance object used by
282 const Tolerance& tolerance() const {
286 /// \name Execution control
287 /// The simplest way to execute the algorithm is to use \ref run().\n
288 /// If you need better control on the initial solution or the execution,
289 /// you have to call one of the \ref init() functions first, then
290 /// \ref start() or multiple times the \ref augment() function.
294 /// \brief Initializes the algorithm.
296 /// Initializes the internal data structures and sets the initial
297 /// flow to zero on each arc.
300 for (ArcIt it(_graph); it != INVALID; ++it) {
306 /// \brief Initializes the algorithm using the given flow map.
308 /// Initializes the internal data structures and sets the initial
309 /// flow to the given \c flowMap. The \c flowMap should
310 /// contain a feasible flow, i.e. at each node excluding the source
311 /// and the target, the incoming flow should be equal to the
313 template <typename FlowMap>
314 void flowInit(const FlowMap& flowMap) {
316 for (ArcIt e(_graph); e != INVALID; ++e) {
317 _flow->set(e, flowMap[e]);
320 for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
321 _flow_value += (*_flow)[jt];
323 for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
324 _flow_value -= (*_flow)[jt];
328 /// \brief Initializes the algorithm using the given flow map.
330 /// Initializes the internal data structures and sets the initial
331 /// flow to the given \c flowMap. The \c flowMap should
332 /// contain a feasible flow, i.e. at each node excluding the source
333 /// and the target, the incoming flow should be equal to the
335 /// \return \c false when the given \c flowMap does not contain a
337 template <typename FlowMap>
338 bool checkedFlowInit(const FlowMap& flowMap) {
340 for (ArcIt e(_graph); e != INVALID; ++e) {
341 _flow->set(e, flowMap[e]);
343 for (NodeIt it(_graph); it != INVALID; ++it) {
344 if (it == _source || it == _target) continue;
346 for (OutArcIt jt(_graph, it); jt != INVALID; ++jt) {
347 outFlow += (*_flow)[jt];
350 for (InArcIt jt(_graph, it); jt != INVALID; ++jt) {
351 inFlow += (*_flow)[jt];
353 if (_tolerance.different(outFlow, inFlow)) {
357 for (ArcIt it(_graph); it != INVALID; ++it) {
358 if (_tolerance.less((*_flow)[it], 0)) return false;
359 if (_tolerance.less((*_capacity)[it], (*_flow)[it])) return false;
362 for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
363 _flow_value += (*_flow)[jt];
365 for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
366 _flow_value -= (*_flow)[jt];
371 /// \brief Augments the solution along a shortest path.
373 /// Augments the solution along a shortest path. This function searches a
374 /// shortest path between the source and the target
375 /// in the residual digraph by the Bfs algoritm.
376 /// Then it increases the flow on this path with the minimal residual
377 /// capacity on the path. If there is no such path, it gives back
379 /// \return \c false when the augmenting did not success, i.e. the
380 /// current flow is a feasible and optimal solution.
382 for (NodeIt n(_graph); n != INVALID; ++n) {
383 _pred->set(n, INVALID);
386 int first = 0, last = 1;
389 _pred->set(_source, OutArcIt(_graph, _source));
391 while (first != last && (*_pred)[_target] == INVALID) {
392 Node n = _queue[first++];
394 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
395 Value rem = (*_capacity)[e] - (*_flow)[e];
396 Node t = _graph.target(e);
397 if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
402 for (InArcIt e(_graph, n); e != INVALID; ++e) {
403 Value rem = (*_flow)[e];
404 Node t = _graph.source(e);
405 if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
412 if ((*_pred)[_target] != INVALID) {
416 Value prem = (*_capacity)[e] - (*_flow)[e];
417 n = _graph.source(e);
418 while (n != _source) {
420 if (_graph.target(e) == n) {
421 Value rem = (*_capacity)[e] - (*_flow)[e];
422 if (rem < prem) prem = rem;
423 n = _graph.source(e);
425 Value rem = (*_flow)[e];
426 if (rem < prem) prem = rem;
427 n = _graph.target(e);
434 _flow->set(e, (*_flow)[e] + prem);
435 n = _graph.source(e);
436 while (n != _source) {
438 if (_graph.target(e) == n) {
439 _flow->set(e, (*_flow)[e] + prem);
440 n = _graph.source(e);
442 _flow->set(e, (*_flow)[e] - prem);
443 n = _graph.target(e);
454 /// \brief Executes the algorithm
456 /// Executes the algorithm by performing augmenting phases until the
457 /// optimal solution is reached.
458 /// \pre One of the \ref init() functions must be called before
459 /// using this function.
464 /// \brief Runs the algorithm.
466 /// Runs the Edmonds-Karp algorithm.
467 /// \note ek.run() is just a shortcut of the following code.
479 /// \name Query Functions
480 /// The result of the Edmonds-Karp algorithm can be obtained using these
482 /// Either \ref run() or \ref start() should be called before using them.
486 /// \brief Returns the value of the maximum flow.
488 /// Returns the value of the maximum flow found by the algorithm.
490 /// \pre Either \ref run() or \ref init() must be called before
491 /// using this function.
492 Value flowValue() const {
496 /// \brief Returns the flow value on the given arc.
498 /// Returns the flow value on the given arc.
500 /// \pre Either \ref run() or \ref init() must be called before
501 /// using this function.
502 Value flow(const Arc& arc) const {
503 return (*_flow)[arc];
506 /// \brief Returns a const reference to the flow map.
508 /// Returns a const reference to the arc map storing the found flow.
510 /// \pre Either \ref run() or \ref init() must be called before
511 /// using this function.
512 const FlowMap& flowMap() const {
516 /// \brief Returns \c true when the node is on the source side of the
519 /// Returns true when the node is on the source side of the found
522 /// \pre Either \ref run() or \ref init() must be called before
523 /// using this function.
524 bool minCut(const Node& node) const {
525 return ((*_pred)[node] != INVALID) or node == _source;
528 /// \brief Gives back a minimum value cut.
530 /// Sets \c cutMap to the characteristic vector of a minimum value
531 /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
532 /// node map with \c bool (or convertible) value type.
534 /// \note This function calls \ref minCut() for each node, so it runs in
537 /// \pre Either \ref run() or \ref init() must be called before
538 /// using this function.
539 template <typename CutMap>
540 void minCutMap(CutMap& cutMap) const {
541 for (NodeIt n(_graph); n != INVALID; ++n) {
542 cutMap.set(n, (*_pred)[n] != INVALID);
544 cutMap.set(_source, true);