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 length of the arcs.
49 typedef typename CapacityMap::Value Value;
51 /// \brief The map type that stores the flow values.
53 /// The map type that stores the flow values.
54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
55 typedef typename Digraph::template ArcMap<Value> FlowMap;
57 /// \brief Instantiates a FlowMap.
59 /// This function instantiates a \ref FlowMap.
60 /// \param digraph The digraph, to which we would like to define the flow map.
61 static FlowMap* createFlowMap(const Digraph& digraph) {
62 return new FlowMap(digraph);
65 /// \brief The tolerance used by the algorithm
67 /// The tolerance used by the algorithm to handle inexact computation.
68 typedef lemon::Tolerance<Value> Tolerance;
74 /// \brief Edmonds-Karp algorithms class.
76 /// This class provides an implementation of the \e Edmonds-Karp \e
77 /// algorithm producing a flow of maximum value in directed
78 /// digraphs. The Edmonds-Karp algorithm is slower than the Preflow
79 /// algorithm but it has an advantage of the step-by-step execution
80 /// control with feasible flow solutions. The \e source node, the \e
81 /// target node, the \e capacity of the arcs and the \e starting \e
82 /// flow value of the arcs should be passed to the algorithm
83 /// through the constructor.
85 /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
86 /// worst case. Always try the preflow algorithm instead of this if
87 /// you just want to compute the optimal flow.
89 /// \param GR The digraph type the algorithm runs on.
90 /// \param CAP The capacity map type.
91 /// \param TR Traits class to set various data types used by
92 /// the algorithm. The default traits class is \ref
93 /// EdmondsKarpDefaultTraits. See \ref EdmondsKarpDefaultTraits for the
94 /// documentation of a Edmonds-Karp traits class.
97 template <typename GR, typename CAP, typename TR>
99 template <typename GR,
100 typename CAP = typename GR::template ArcMap<int>,
101 typename TR = EdmondsKarpDefaultTraits<GR, CAP> >
107 typedef typename Traits::Digraph Digraph;
108 typedef typename Traits::CapacityMap CapacityMap;
109 typedef typename Traits::Value Value;
111 typedef typename Traits::FlowMap FlowMap;
112 typedef typename Traits::Tolerance Tolerance;
116 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
117 typedef typename Digraph::template NodeMap<Arc> PredMap;
119 const Digraph& _graph;
120 const CapacityMap* _capacity;
122 Node _source, _target;
128 std::vector<Node> _queue;
130 Tolerance _tolerance;
133 void createStructures() {
135 _flow = Traits::createFlowMap(_graph);
139 _pred = new PredMap(_graph);
141 _queue.resize(countNodes(_graph));
144 void destroyStructures() {
155 ///\name Named template parameters
159 template <typename T>
160 struct DefFlowMapTraits : public Traits {
162 static FlowMap *createFlowMap(const Digraph&) {
163 LEMON_ASSERT(false,"Uninitialized parameter.");
168 /// \brief \ref named-templ-param "Named parameter" for setting
171 /// \ref named-templ-param "Named parameter" for setting FlowMap
173 template <typename T>
175 : public EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> > {
176 typedef EdmondsKarp<Digraph, CapacityMap, DefFlowMapTraits<T> >
189 /// \brief The constructor of the class.
191 /// The constructor of the class.
192 /// \param digraph The digraph the algorithm runs on.
193 /// \param capacity The capacity of the arcs.
194 /// \param source The source node.
195 /// \param target The target node.
196 EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity,
197 Node source, Node target)
198 : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
199 _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
201 LEMON_ASSERT(_source != _target,"Flow source and target are the same nodes.");
204 /// \brief Destructor.
211 /// \brief Sets the capacity map.
213 /// Sets the capacity map.
214 /// \return \c (*this)
215 EdmondsKarp& capacityMap(const CapacityMap& map) {
220 /// \brief Sets the flow map.
222 /// Sets the flow map.
223 /// \return \c (*this)
224 EdmondsKarp& flowMap(FlowMap& map) {
233 /// \brief Returns the flow map.
235 /// \return The flow map.
236 const FlowMap& flowMap() const {
240 /// \brief Sets the source node.
242 /// Sets the source node.
243 /// \return \c (*this)
244 EdmondsKarp& source(const Node& node) {
249 /// \brief Sets the target node.
251 /// Sets the target node.
252 /// \return \c (*this)
253 EdmondsKarp& target(const Node& node) {
258 /// \brief Sets the tolerance used by algorithm.
260 /// Sets the tolerance used by algorithm.
261 EdmondsKarp& tolerance(const Tolerance& tolerance) {
262 _tolerance = tolerance;
266 /// \brief Returns the tolerance used by algorithm.
268 /// Returns the tolerance used by algorithm.
269 const Tolerance& tolerance() const {
273 /// \name Execution control
274 /// The simplest way to execute the
275 /// algorithm is to use the \c run() member functions.
277 /// If you need more control on initial solution or
278 /// execution then you have to call one \ref init() function and then
279 /// the start() or multiple times the \c augment() member function.
283 /// \brief Initializes the algorithm
285 /// Sets the flow to empty flow.
288 for (ArcIt it(_graph); it != INVALID; ++it) {
294 /// \brief Initializes the algorithm
296 /// Initializes the flow to the \c flowMap. The \c flowMap should
297 /// contain a feasible flow, ie. in each node excluding the source
298 /// and the target the incoming flow should be equal to the
300 template <typename FlowMap>
301 void flowInit(const FlowMap& flowMap) {
303 for (ArcIt e(_graph); e != INVALID; ++e) {
304 _flow->set(e, flowMap[e]);
307 for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
308 _flow_value += (*_flow)[jt];
310 for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
311 _flow_value -= (*_flow)[jt];
315 /// \brief Initializes the algorithm
317 /// Initializes the flow to the \c flowMap. The \c flowMap should
318 /// contain a feasible flow, ie. in each node excluding the source
319 /// and the target the incoming flow should be equal to the
321 /// \return %False when the given flowMap does not contain
323 template <typename FlowMap>
324 bool checkedFlowInit(const FlowMap& flowMap) {
326 for (ArcIt e(_graph); e != INVALID; ++e) {
327 _flow->set(e, flowMap[e]);
329 for (NodeIt it(_graph); it != INVALID; ++it) {
330 if (it == _source || it == _target) continue;
332 for (OutArcIt jt(_graph, it); jt != INVALID; ++jt) {
333 outFlow += (*_flow)[jt];
336 for (InArcIt jt(_graph, it); jt != INVALID; ++jt) {
337 inFlow += (*_flow)[jt];
339 if (_tolerance.different(outFlow, inFlow)) {
343 for (ArcIt it(_graph); it != INVALID; ++it) {
344 if (_tolerance.less((*_flow)[it], 0)) return false;
345 if (_tolerance.less((*_capacity)[it], (*_flow)[it])) return false;
348 for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
349 _flow_value += (*_flow)[jt];
351 for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
352 _flow_value -= (*_flow)[jt];
357 /// \brief Augment the solution on an arc shortest path.
359 /// Augment the solution on an arc shortest path. It searches an
360 /// arc shortest path between the source and the target
361 /// in the residual digraph by the bfs algoritm.
362 /// Then it increases the flow on this path with the minimal residual
363 /// capacity on the path. If there is no such path it gives back
365 /// \return %False when the augmenting didn't success so the
366 /// current flow is a feasible and optimal solution.
368 for (NodeIt n(_graph); n != INVALID; ++n) {
369 _pred->set(n, INVALID);
372 int first = 0, last = 1;
375 _pred->set(_source, OutArcIt(_graph, _source));
377 while (first != last && (*_pred)[_target] == INVALID) {
378 Node n = _queue[first++];
380 for (OutArcIt e(_graph, n); e != INVALID; ++e) {
381 Value rem = (*_capacity)[e] - (*_flow)[e];
382 Node t = _graph.target(e);
383 if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
388 for (InArcIt e(_graph, n); e != INVALID; ++e) {
389 Value rem = (*_flow)[e];
390 Node t = _graph.source(e);
391 if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
398 if ((*_pred)[_target] != INVALID) {
402 Value prem = (*_capacity)[e] - (*_flow)[e];
403 n = _graph.source(e);
404 while (n != _source) {
406 if (_graph.target(e) == n) {
407 Value rem = (*_capacity)[e] - (*_flow)[e];
408 if (rem < prem) prem = rem;
409 n = _graph.source(e);
411 Value rem = (*_flow)[e];
412 if (rem < prem) prem = rem;
413 n = _graph.target(e);
420 _flow->set(e, (*_flow)[e] + prem);
421 n = _graph.source(e);
422 while (n != _source) {
424 if (_graph.target(e) == n) {
425 _flow->set(e, (*_flow)[e] + prem);
426 n = _graph.source(e);
428 _flow->set(e, (*_flow)[e] - prem);
429 n = _graph.target(e);
440 /// \brief Executes the algorithm
442 /// It runs augmenting phases until the optimal solution is reached.
447 /// \brief Runs the algorithm.
449 /// It is just a shorthand for:
462 /// \name Query Functions
463 /// The result of the Edmonds-Karp algorithm can be obtained using these
465 /// Before the use of these functions,
466 /// either run() or start() must be called.
470 /// \brief Returns the value of the maximum flow.
472 /// Returns the value of the maximum flow by returning the excess
473 /// of the target node \c t.
475 Value flowValue() const {
480 /// \brief Returns the flow on the arc.
482 /// Sets the \c flowMap to the flow on the arcs.
483 Value flow(const Arc& arc) const {
484 return (*_flow)[arc];
487 /// \brief Returns true when the node is on the source side of minimum cut.
490 /// Returns true when the node is on the source side of minimum
493 bool minCut(const Node& node) const {
494 return ((*_pred)[node] != INVALID) or node == _source;
497 /// \brief Returns a minimum value cut.
499 /// Sets \c cutMap to the characteristic vector of a minimum value cut.
501 template <typename CutMap>
502 void minCutMap(CutMap& cutMap) const {
503 for (NodeIt n(_graph); n != INVALID; ++n) {
504 cutMap.set(n, (*_pred)[n] != INVALID);
506 cutMap.set(_source, true);