thoneyvazul@1056: /* -*- mode: C++; indent-tabs-mode: nil; -*-
thoneyvazul@1056:  *
thoneyvazul@1056:  * This file is a part of LEMON, a generic C++ optimization library.
thoneyvazul@1056:  *
alpar@1092:  * Copyright (C) 2003-2013
thoneyvazul@1056:  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
thoneyvazul@1056:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
thoneyvazul@1056:  *
thoneyvazul@1056:  * Permission to use, modify and distribute this software is granted
thoneyvazul@1056:  * provided that this copyright notice appears in all copies. For
thoneyvazul@1056:  * precise terms see the accompanying LICENSE file.
thoneyvazul@1056:  *
thoneyvazul@1056:  * This software is provided "AS IS" with no warranty of any kind,
thoneyvazul@1056:  * express or implied, and with no claim as to its suitability for any
thoneyvazul@1056:  * purpose.
thoneyvazul@1056:  *
thoneyvazul@1056:  */
thoneyvazul@1056: 
thoneyvazul@1056: #ifndef LEMON_EDMONDS_KARP_H
thoneyvazul@1056: #define LEMON_EDMONDS_KARP_H
thoneyvazul@1056: 
thoneyvazul@1056: /// \file
thoneyvazul@1056: /// \ingroup max_flow
thoneyvazul@1056: /// \brief Implementation of the Edmonds-Karp algorithm.
thoneyvazul@1056: 
thoneyvazul@1056: #include <lemon/tolerance.h>
thoneyvazul@1056: #include <vector>
thoneyvazul@1056: 
thoneyvazul@1056: namespace lemon {
thoneyvazul@1056: 
thoneyvazul@1056:   /// \brief Default traits class of EdmondsKarp class.
thoneyvazul@1056:   ///
thoneyvazul@1056:   /// Default traits class of EdmondsKarp class.
thoneyvazul@1056:   /// \param GR Digraph type.
thoneyvazul@1056:   /// \param CAP Type of capacity map.
thoneyvazul@1056:   template <typename GR, typename CAP>
thoneyvazul@1056:   struct EdmondsKarpDefaultTraits {
thoneyvazul@1056: 
alpar@1092:     /// \brief The digraph type the algorithm runs on.
thoneyvazul@1056:     typedef GR Digraph;
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief The type of the map that stores the arc capacities.
thoneyvazul@1056:     ///
thoneyvazul@1056:     /// The type of the map that stores the arc capacities.
thoneyvazul@1056:     /// It must meet the \ref concepts::ReadMap "ReadMap" concept.
thoneyvazul@1056:     typedef CAP CapacityMap;
thoneyvazul@1056: 
kpeter@1057:     /// \brief The type of the flow values.
thoneyvazul@1056:     typedef typename CapacityMap::Value Value;
thoneyvazul@1056: 
kpeter@1057:     /// \brief The type of the map that stores the flow values.
thoneyvazul@1056:     ///
kpeter@1057:     /// The type of the map that stores the flow values.
thoneyvazul@1056:     /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
kpeter@1057: #ifdef DOXYGEN
kpeter@1057:     typedef GR::ArcMap<Value> FlowMap;
kpeter@1057: #else
thoneyvazul@1056:     typedef typename Digraph::template ArcMap<Value> FlowMap;
kpeter@1057: #endif
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Instantiates a FlowMap.
thoneyvazul@1056:     ///
alpar@1092:     /// This function instantiates a \ref FlowMap.
kpeter@1057:     /// \param digraph The digraph for which we would like to define
kpeter@1057:     /// the flow map.
thoneyvazul@1056:     static FlowMap* createFlowMap(const Digraph& digraph) {
thoneyvazul@1056:       return new FlowMap(digraph);
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief The tolerance used by the algorithm
thoneyvazul@1056:     ///
thoneyvazul@1056:     /// The tolerance used by the algorithm to handle inexact computation.
thoneyvazul@1056:     typedef lemon::Tolerance<Value> Tolerance;
thoneyvazul@1056: 
thoneyvazul@1056:   };
thoneyvazul@1056: 
thoneyvazul@1056:   /// \ingroup max_flow
thoneyvazul@1056:   ///
thoneyvazul@1056:   /// \brief Edmonds-Karp algorithms class.
thoneyvazul@1056:   ///
thoneyvazul@1056:   /// This class provides an implementation of the \e Edmonds-Karp \e
kpeter@1057:   /// algorithm producing a \ref max_flow "flow of maximum value" in a
alpar@1074:   /// digraph \cite clrs01algorithms, \cite amo93networkflows,
alpar@1074:   /// \cite edmondskarp72theoretical.
kpeter@1057:   /// The Edmonds-Karp algorithm is slower than the Preflow
kpeter@1057:   /// algorithm, but it has an advantage of the step-by-step execution
thoneyvazul@1056:   /// control with feasible flow solutions. The \e source node, the \e
thoneyvazul@1056:   /// target node, the \e capacity of the arcs and the \e starting \e
thoneyvazul@1056:   /// flow value of the arcs should be passed to the algorithm
thoneyvazul@1056:   /// through the constructor.
thoneyvazul@1056:   ///
thoneyvazul@1056:   /// The time complexity of the algorithm is \f$ O(nm^2) \f$ in
kpeter@1057:   /// worst case. Always try the Preflow algorithm instead of this if
thoneyvazul@1056:   /// you just want to compute the optimal flow.
thoneyvazul@1056:   ///
kpeter@1057:   /// \tparam GR The type of the digraph the algorithm runs on.
kpeter@1057:   /// \tparam CAP The type of the capacity map. The default map
alpar@1092:   /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
kpeter@1057:   /// \tparam TR The traits class that defines various types used by the
kpeter@1057:   /// algorithm. By default, it is \ref EdmondsKarpDefaultTraits
kpeter@1057:   /// "EdmondsKarpDefaultTraits<GR, CAP>".
kpeter@1057:   /// In most cases, this parameter should not be set directly,
kpeter@1057:   /// consider to use the named template parameters instead.
thoneyvazul@1056: 
thoneyvazul@1056: #ifdef DOXYGEN
thoneyvazul@1056:   template <typename GR, typename CAP, typename TR>
alpar@1092: #else
thoneyvazul@1056:   template <typename GR,
alpar@1092:             typename CAP = typename GR::template ArcMap<int>,
thoneyvazul@1056:             typename TR = EdmondsKarpDefaultTraits<GR, CAP> >
thoneyvazul@1056: #endif
thoneyvazul@1056:   class EdmondsKarp {
thoneyvazul@1056:   public:
thoneyvazul@1056: 
alpar@1074:     /// \brief The \ref lemon::EdmondsKarpDefaultTraits "traits class"
alpar@1074:     /// of the algorithm.
thoneyvazul@1056:     typedef TR Traits;
kpeter@1057:     /// The type of the digraph the algorithm runs on.
thoneyvazul@1056:     typedef typename Traits::Digraph Digraph;
kpeter@1057:     /// The type of the capacity map.
thoneyvazul@1056:     typedef typename Traits::CapacityMap CapacityMap;
kpeter@1057:     /// The type of the flow values.
alpar@1092:     typedef typename Traits::Value Value;
thoneyvazul@1056: 
kpeter@1057:     /// The type of the flow map.
thoneyvazul@1056:     typedef typename Traits::FlowMap FlowMap;
kpeter@1057:     /// The type of the tolerance.
thoneyvazul@1056:     typedef typename Traits::Tolerance Tolerance;
thoneyvazul@1056: 
thoneyvazul@1056:   private:
thoneyvazul@1056: 
thoneyvazul@1056:     TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
thoneyvazul@1056:     typedef typename Digraph::template NodeMap<Arc> PredMap;
alpar@1092: 
thoneyvazul@1056:     const Digraph& _graph;
thoneyvazul@1056:     const CapacityMap* _capacity;
thoneyvazul@1056: 
thoneyvazul@1056:     Node _source, _target;
thoneyvazul@1056: 
thoneyvazul@1056:     FlowMap* _flow;
thoneyvazul@1056:     bool _local_flow;
thoneyvazul@1056: 
thoneyvazul@1056:     PredMap* _pred;
thoneyvazul@1056:     std::vector<Node> _queue;
alpar@1092: 
thoneyvazul@1056:     Tolerance _tolerance;
thoneyvazul@1056:     Value _flow_value;
thoneyvazul@1056: 
thoneyvazul@1056:     void createStructures() {
thoneyvazul@1056:       if (!_flow) {
alpar@1092:         _flow = Traits::createFlowMap(_graph);
alpar@1092:         _local_flow = true;
thoneyvazul@1056:       }
thoneyvazul@1056:       if (!_pred) {
alpar@1092:         _pred = new PredMap(_graph);
thoneyvazul@1056:       }
thoneyvazul@1056:       _queue.resize(countNodes(_graph));
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     void destroyStructures() {
thoneyvazul@1056:       if (_local_flow) {
alpar@1092:         delete _flow;
thoneyvazul@1056:       }
thoneyvazul@1056:       if (_pred) {
alpar@1092:         delete _pred;
thoneyvazul@1056:       }
thoneyvazul@1056:     }
alpar@1092: 
thoneyvazul@1056:   public:
thoneyvazul@1056: 
kpeter@1060:     typedef EdmondsKarp Create;
kpeter@1060: 
thoneyvazul@1056:     ///\name Named template parameters
thoneyvazul@1056: 
thoneyvazul@1056:     ///@{
thoneyvazul@1056: 
thoneyvazul@1056:     template <typename T>
kpeter@1058:     struct SetFlowMapTraits : public Traits {
thoneyvazul@1056:       typedef T FlowMap;
thoneyvazul@1056:       static FlowMap *createFlowMap(const Digraph&) {
alpar@1092:         LEMON_ASSERT(false, "FlowMap is not initialized");
thoneyvazul@1056:         return 0;
thoneyvazul@1056:       }
thoneyvazul@1056:     };
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief \ref named-templ-param "Named parameter" for setting
thoneyvazul@1056:     /// FlowMap type
thoneyvazul@1056:     ///
thoneyvazul@1056:     /// \ref named-templ-param "Named parameter" for setting FlowMap
thoneyvazul@1056:     /// type
thoneyvazul@1056:     template <typename T>
alpar@1092:     struct SetFlowMap
kpeter@1058:       : public EdmondsKarp<Digraph, CapacityMap, SetFlowMapTraits<T> > {
kpeter@1058:       typedef EdmondsKarp<Digraph, CapacityMap, SetFlowMapTraits<T> > Create;
thoneyvazul@1056:     };
thoneyvazul@1056: 
thoneyvazul@1056:     /// @}
thoneyvazul@1056: 
thoneyvazul@1056:   protected:
alpar@1092: 
thoneyvazul@1056:     EdmondsKarp() {}
thoneyvazul@1056: 
thoneyvazul@1056:   public:
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief The constructor of the class.
thoneyvazul@1056:     ///
alpar@1092:     /// The constructor of the class.
alpar@1092:     /// \param digraph The digraph the algorithm runs on.
alpar@1092:     /// \param capacity The capacity of the arcs.
thoneyvazul@1056:     /// \param source The source node.
thoneyvazul@1056:     /// \param target The target node.
thoneyvazul@1056:     EdmondsKarp(const Digraph& digraph, const CapacityMap& capacity,
alpar@1092:                 Node source, Node target)
thoneyvazul@1056:       : _graph(digraph), _capacity(&capacity), _source(source), _target(target),
alpar@1092:         _flow(0), _local_flow(false), _pred(0), _tolerance(), _flow_value()
thoneyvazul@1056:     {
kpeter@1057:       LEMON_ASSERT(_source != _target,
kpeter@1057:                    "Flow source and target are the same nodes.");
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Destructor.
thoneyvazul@1056:     ///
thoneyvazul@1056:     /// Destructor.
thoneyvazul@1056:     ~EdmondsKarp() {
thoneyvazul@1056:       destroyStructures();
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Sets the capacity map.
thoneyvazul@1056:     ///
thoneyvazul@1056:     /// Sets the capacity map.
kpeter@1057:     /// \return <tt>(*this)</tt>
thoneyvazul@1056:     EdmondsKarp& capacityMap(const CapacityMap& map) {
thoneyvazul@1056:       _capacity = &map;
thoneyvazul@1056:       return *this;
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Sets the flow map.
thoneyvazul@1056:     ///
thoneyvazul@1056:     /// Sets the flow map.
kpeter@1057:     /// If you don't use this function before calling \ref run() or
kpeter@1057:     /// \ref init(), an instance will be allocated automatically.
kpeter@1057:     /// The destructor deallocates this automatically allocated map,
kpeter@1057:     /// of course.
kpeter@1057:     /// \return <tt>(*this)</tt>
thoneyvazul@1056:     EdmondsKarp& flowMap(FlowMap& map) {
thoneyvazul@1056:       if (_local_flow) {
alpar@1092:         delete _flow;
alpar@1092:         _local_flow = false;
thoneyvazul@1056:       }
thoneyvazul@1056:       _flow = &map;
thoneyvazul@1056:       return *this;
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Sets the source node.
thoneyvazul@1056:     ///
thoneyvazul@1056:     /// Sets the source node.
kpeter@1057:     /// \return <tt>(*this)</tt>
thoneyvazul@1056:     EdmondsKarp& source(const Node& node) {
thoneyvazul@1056:       _source = node;
thoneyvazul@1056:       return *this;
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Sets the target node.
thoneyvazul@1056:     ///
thoneyvazul@1056:     /// Sets the target node.
kpeter@1057:     /// \return <tt>(*this)</tt>
thoneyvazul@1056:     EdmondsKarp& target(const Node& node) {
thoneyvazul@1056:       _target = node;
thoneyvazul@1056:       return *this;
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Sets the tolerance used by algorithm.
thoneyvazul@1056:     ///
thoneyvazul@1056:     /// Sets the tolerance used by algorithm.
kpeter@1057:     /// \return <tt>(*this)</tt>
thoneyvazul@1056:     EdmondsKarp& tolerance(const Tolerance& tolerance) {
thoneyvazul@1056:       _tolerance = tolerance;
thoneyvazul@1056:       return *this;
alpar@1092:     }
thoneyvazul@1056: 
kpeter@1057:     /// \brief Returns a const reference to the tolerance.
thoneyvazul@1056:     ///
kpeter@1057:     /// Returns a const reference to the tolerance object used by
kpeter@1057:     /// the algorithm.
thoneyvazul@1056:     const Tolerance& tolerance() const {
thoneyvazul@1056:       return _tolerance;
alpar@1092:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \name Execution control
kpeter@1057:     /// The simplest way to execute the algorithm is to use \ref run().\n
kpeter@1057:     /// If you need better control on the initial solution or the execution,
kpeter@1057:     /// you have to call one of the \ref init() functions first, then
kpeter@1057:     /// \ref start() or multiple times the \ref augment() function.
alpar@1092: 
thoneyvazul@1056:     ///@{
thoneyvazul@1056: 
kpeter@1057:     /// \brief Initializes the algorithm.
kpeter@1057:     ///
kpeter@1057:     /// Initializes the internal data structures and sets the initial
kpeter@1057:     /// flow to zero on each arc.
thoneyvazul@1056:     void init() {
thoneyvazul@1056:       createStructures();
thoneyvazul@1056:       for (ArcIt it(_graph); it != INVALID; ++it) {
thoneyvazul@1056:         _flow->set(it, 0);
thoneyvazul@1056:       }
thoneyvazul@1056:       _flow_value = 0;
thoneyvazul@1056:     }
alpar@1092: 
kpeter@1057:     /// \brief Initializes the algorithm using the given flow map.
kpeter@1057:     ///
kpeter@1057:     /// Initializes the internal data structures and sets the initial
kpeter@1057:     /// flow to the given \c flowMap. The \c flowMap should
kpeter@1057:     /// contain a feasible flow, i.e. at each node excluding the source
kpeter@1057:     /// and the target, the incoming flow should be equal to the
thoneyvazul@1056:     /// outgoing flow.
thoneyvazul@1056:     template <typename FlowMap>
kpeter@1059:     void init(const FlowMap& flowMap) {
thoneyvazul@1056:       createStructures();
thoneyvazul@1056:       for (ArcIt e(_graph); e != INVALID; ++e) {
alpar@1092:         _flow->set(e, flowMap[e]);
thoneyvazul@1056:       }
thoneyvazul@1056:       _flow_value = 0;
thoneyvazul@1056:       for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
thoneyvazul@1056:         _flow_value += (*_flow)[jt];
thoneyvazul@1056:       }
thoneyvazul@1056:       for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
thoneyvazul@1056:         _flow_value -= (*_flow)[jt];
thoneyvazul@1056:       }
thoneyvazul@1056:     }
thoneyvazul@1056: 
kpeter@1057:     /// \brief Initializes the algorithm using the given flow map.
kpeter@1057:     ///
kpeter@1057:     /// Initializes the internal data structures and sets the initial
kpeter@1057:     /// flow to the given \c flowMap. The \c flowMap should
kpeter@1057:     /// contain a feasible flow, i.e. at each node excluding the source
kpeter@1057:     /// and the target, the incoming flow should be equal to the
alpar@1092:     /// outgoing flow.
kpeter@1057:     /// \return \c false when the given \c flowMap does not contain a
thoneyvazul@1056:     /// feasible flow.
thoneyvazul@1056:     template <typename FlowMap>
kpeter@1059:     bool checkedInit(const FlowMap& flowMap) {
thoneyvazul@1056:       createStructures();
thoneyvazul@1056:       for (ArcIt e(_graph); e != INVALID; ++e) {
alpar@1092:         _flow->set(e, flowMap[e]);
thoneyvazul@1056:       }
thoneyvazul@1056:       for (NodeIt it(_graph); it != INVALID; ++it) {
thoneyvazul@1056:         if (it == _source || it == _target) continue;
thoneyvazul@1056:         Value outFlow = 0;
thoneyvazul@1056:         for (OutArcIt jt(_graph, it); jt != INVALID; ++jt) {
thoneyvazul@1056:           outFlow += (*_flow)[jt];
thoneyvazul@1056:         }
thoneyvazul@1056:         Value inFlow = 0;
thoneyvazul@1056:         for (InArcIt jt(_graph, it); jt != INVALID; ++jt) {
thoneyvazul@1056:           inFlow += (*_flow)[jt];
thoneyvazul@1056:         }
thoneyvazul@1056:         if (_tolerance.different(outFlow, inFlow)) {
thoneyvazul@1056:           return false;
thoneyvazul@1056:         }
thoneyvazul@1056:       }
thoneyvazul@1056:       for (ArcIt it(_graph); it != INVALID; ++it) {
thoneyvazul@1056:         if (_tolerance.less((*_flow)[it], 0)) return false;
thoneyvazul@1056:         if (_tolerance.less((*_capacity)[it], (*_flow)[it])) return false;
thoneyvazul@1056:       }
thoneyvazul@1056:       _flow_value = 0;
thoneyvazul@1056:       for (OutArcIt jt(_graph, _source); jt != INVALID; ++jt) {
thoneyvazul@1056:         _flow_value += (*_flow)[jt];
thoneyvazul@1056:       }
thoneyvazul@1056:       for (InArcIt jt(_graph, _source); jt != INVALID; ++jt) {
thoneyvazul@1056:         _flow_value -= (*_flow)[jt];
thoneyvazul@1056:       }
thoneyvazul@1056:       return true;
thoneyvazul@1056:     }
thoneyvazul@1056: 
kpeter@1057:     /// \brief Augments the solution along a shortest path.
alpar@1092:     ///
kpeter@1057:     /// Augments the solution along a shortest path. This function searches a
kpeter@1057:     /// shortest path between the source and the target
kpeter@1057:     /// in the residual digraph by the Bfs algoritm.
thoneyvazul@1056:     /// Then it increases the flow on this path with the minimal residual
kpeter@1057:     /// capacity on the path. If there is no such path, it gives back
thoneyvazul@1056:     /// false.
kpeter@1057:     /// \return \c false when the augmenting did not success, i.e. the
thoneyvazul@1056:     /// current flow is a feasible and optimal solution.
thoneyvazul@1056:     bool augment() {
thoneyvazul@1056:       for (NodeIt n(_graph); n != INVALID; ++n) {
alpar@1092:         _pred->set(n, INVALID);
thoneyvazul@1056:       }
alpar@1092: 
thoneyvazul@1056:       int first = 0, last = 1;
alpar@1092: 
thoneyvazul@1056:       _queue[0] = _source;
thoneyvazul@1056:       _pred->set(_source, OutArcIt(_graph, _source));
thoneyvazul@1056: 
thoneyvazul@1056:       while (first != last && (*_pred)[_target] == INVALID) {
alpar@1092:         Node n = _queue[first++];
alpar@1092: 
alpar@1092:         for (OutArcIt e(_graph, n); e != INVALID; ++e) {
alpar@1092:           Value rem = (*_capacity)[e] - (*_flow)[e];
alpar@1092:           Node t = _graph.target(e);
alpar@1092:           if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
alpar@1092:             _pred->set(t, e);
alpar@1092:             _queue[last++] = t;
alpar@1092:           }
alpar@1092:         }
alpar@1092:         for (InArcIt e(_graph, n); e != INVALID; ++e) {
alpar@1092:           Value rem = (*_flow)[e];
alpar@1092:           Node t = _graph.source(e);
alpar@1092:           if (_tolerance.positive(rem) && (*_pred)[t] == INVALID) {
alpar@1092:             _pred->set(t, e);
alpar@1092:             _queue[last++] = t;
alpar@1092:           }
alpar@1092:         }
thoneyvazul@1056:       }
thoneyvazul@1056: 
thoneyvazul@1056:       if ((*_pred)[_target] != INVALID) {
alpar@1092:         Node n = _target;
alpar@1092:         Arc e = (*_pred)[n];
thoneyvazul@1056: 
alpar@1092:         Value prem = (*_capacity)[e] - (*_flow)[e];
alpar@1092:         n = _graph.source(e);
alpar@1092:         while (n != _source) {
alpar@1092:           e = (*_pred)[n];
alpar@1092:           if (_graph.target(e) == n) {
alpar@1092:             Value rem = (*_capacity)[e] - (*_flow)[e];
alpar@1092:             if (rem < prem) prem = rem;
alpar@1092:             n = _graph.source(e);
alpar@1092:           } else {
alpar@1092:             Value rem = (*_flow)[e];
alpar@1092:             if (rem < prem) prem = rem;
alpar@1092:             n = _graph.target(e);
alpar@1092:           }
alpar@1092:         }
thoneyvazul@1056: 
alpar@1092:         n = _target;
alpar@1092:         e = (*_pred)[n];
thoneyvazul@1056: 
alpar@1092:         _flow->set(e, (*_flow)[e] + prem);
alpar@1092:         n = _graph.source(e);
alpar@1092:         while (n != _source) {
alpar@1092:           e = (*_pred)[n];
alpar@1092:           if (_graph.target(e) == n) {
alpar@1092:             _flow->set(e, (*_flow)[e] + prem);
alpar@1092:             n = _graph.source(e);
alpar@1092:           } else {
alpar@1092:             _flow->set(e, (*_flow)[e] - prem);
alpar@1092:             n = _graph.target(e);
alpar@1092:           }
alpar@1092:         }
thoneyvazul@1056: 
alpar@1092:         _flow_value += prem;
alpar@1092:         return true;
thoneyvazul@1056:       } else {
alpar@1092:         return false;
thoneyvazul@1056:       }
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Executes the algorithm
thoneyvazul@1056:     ///
kpeter@1057:     /// Executes the algorithm by performing augmenting phases until the
alpar@1092:     /// optimal solution is reached.
kpeter@1057:     /// \pre One of the \ref init() functions must be called before
kpeter@1057:     /// using this function.
thoneyvazul@1056:     void start() {
thoneyvazul@1056:       while (augment()) {}
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Runs the algorithm.
alpar@1092:     ///
kpeter@1057:     /// Runs the Edmonds-Karp algorithm.
kpeter@1057:     /// \note ek.run() is just a shortcut of the following code.
alpar@1092:     ///\code
thoneyvazul@1056:     /// ek.init();
thoneyvazul@1056:     /// ek.start();
thoneyvazul@1056:     ///\endcode
thoneyvazul@1056:     void run() {
thoneyvazul@1056:       init();
thoneyvazul@1056:       start();
thoneyvazul@1056:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// @}
thoneyvazul@1056: 
thoneyvazul@1056:     /// \name Query Functions
thoneyvazul@1056:     /// The result of the Edmonds-Karp algorithm can be obtained using these
thoneyvazul@1056:     /// functions.\n
kpeter@1057:     /// Either \ref run() or \ref start() should be called before using them.
alpar@1092: 
thoneyvazul@1056:     ///@{
thoneyvazul@1056: 
thoneyvazul@1056:     /// \brief Returns the value of the maximum flow.
thoneyvazul@1056:     ///
kpeter@1057:     /// Returns the value of the maximum flow found by the algorithm.
kpeter@1057:     ///
kpeter@1057:     /// \pre Either \ref run() or \ref init() must be called before
kpeter@1057:     /// using this function.
thoneyvazul@1056:     Value flowValue() const {
thoneyvazul@1056:       return _flow_value;
thoneyvazul@1056:     }
thoneyvazul@1056: 
kpeter@1057:     /// \brief Returns the flow value on the given arc.
thoneyvazul@1056:     ///
kpeter@1057:     /// Returns the flow value on the given arc.
kpeter@1057:     ///
kpeter@1057:     /// \pre Either \ref run() or \ref init() must be called before
kpeter@1057:     /// using this function.
thoneyvazul@1056:     Value flow(const Arc& arc) const {
thoneyvazul@1056:       return (*_flow)[arc];
thoneyvazul@1056:     }
thoneyvazul@1056: 
kpeter@1057:     /// \brief Returns a const reference to the flow map.
thoneyvazul@1056:     ///
kpeter@1057:     /// Returns a const reference to the arc map storing the found flow.
kpeter@1057:     ///
kpeter@1057:     /// \pre Either \ref run() or \ref init() must be called before
kpeter@1057:     /// using this function.
kpeter@1057:     const FlowMap& flowMap() const {
kpeter@1057:       return *_flow;
kpeter@1057:     }
thoneyvazul@1056: 
kpeter@1057:     /// \brief Returns \c true when the node is on the source side of the
kpeter@1057:     /// minimum cut.
kpeter@1057:     ///
kpeter@1057:     /// Returns true when the node is on the source side of the found
kpeter@1057:     /// minimum cut.
kpeter@1057:     ///
kpeter@1057:     /// \pre Either \ref run() or \ref init() must be called before
kpeter@1057:     /// using this function.
thoneyvazul@1056:     bool minCut(const Node& node) const {
kpeter@1061:       return ((*_pred)[node] != INVALID) || node == _source;
thoneyvazul@1056:     }
thoneyvazul@1056: 
kpeter@1057:     /// \brief Gives back a minimum value cut.
thoneyvazul@1056:     ///
kpeter@1057:     /// Sets \c cutMap to the characteristic vector of a minimum value
kpeter@1057:     /// cut. \c cutMap should be a \ref concepts::WriteMap "writable"
kpeter@1057:     /// node map with \c bool (or convertible) value type.
kpeter@1057:     ///
kpeter@1057:     /// \note This function calls \ref minCut() for each node, so it runs in
kpeter@1057:     /// O(n) time.
kpeter@1057:     ///
kpeter@1057:     /// \pre Either \ref run() or \ref init() must be called before
kpeter@1057:     /// using this function.
thoneyvazul@1056:     template <typename CutMap>
thoneyvazul@1056:     void minCutMap(CutMap& cutMap) const {
thoneyvazul@1056:       for (NodeIt n(_graph); n != INVALID; ++n) {
alpar@1092:         cutMap.set(n, (*_pred)[n] != INVALID);
thoneyvazul@1056:       }
thoneyvazul@1056:       cutMap.set(_source, true);
alpar@1092:     }
thoneyvazul@1056: 
thoneyvazul@1056:     /// @}
thoneyvazul@1056: 
thoneyvazul@1056:   };
thoneyvazul@1056: 
thoneyvazul@1056: }
thoneyvazul@1056: 
thoneyvazul@1056: #endif